read_fonts/collections/int_set/
bitpage.rs

1//! Stores a page of bits, used inside of bitset's.
2
3use alloc::vec::Vec;
4use std::{hash::Hash, ops::RangeInclusive};
5
6// the integer type underlying our bit set
7type Element = u64;
8
9// the number of elements in a page
10const PAGE_SIZE: u32 = 8;
11// the length of an element in bytes
12const ELEM_SIZE: u32 = std::mem::size_of::<Element>() as u32;
13// the length of an element in bits
14const ELEM_BITS: u32 = ELEM_SIZE * 8;
15// mask out bits of a value not used to index into an element
16const ELEM_MASK: u32 = ELEM_BITS - 1;
17// the number of bits in a page
18pub(crate) const PAGE_BITS: u32 = ELEM_BITS * PAGE_SIZE;
19// mask out the bits of a value not used to index into a page
20const PAGE_MASK: u32 = PAGE_BITS - 1;
21
22/// A fixed size (512 bits wide) page of bits that records integer set membership from `[0, 511]`.
23#[derive(Clone)]
24#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
25pub(crate) struct BitPage {
26    storage: [Element; PAGE_SIZE as usize],
27    length: u32,
28}
29
30impl BitPage {
31    /// Create a new page with no bits set.
32    pub(crate) fn new_zeroes() -> Self {
33        Self {
34            storage: [0; PAGE_SIZE as usize],
35            length: 0,
36        }
37    }
38
39    pub(crate) fn recompute_length(&mut self) {
40        self.length = self.storage.iter().copied().map(u64::count_ones).sum();
41    }
42
43    /// Returns the number of members in this page.
44    pub(crate) fn len(&self) -> u32 {
45        self.length
46    }
47
48    /// Returns true if this page has no members.
49    pub(crate) fn is_empty(&self) -> bool {
50        self.len() == 0
51    }
52
53    /// Returns true if this page has any members in common with `other`.
54    pub(crate) fn intersects_set(&self, other: &BitPage) -> bool {
55        for (a, b) in self.storage.iter().zip(other.storage.iter()) {
56            if (*a & *b) != 0 {
57                return true;
58            }
59        }
60        false
61    }
62
63    // TODO(garretrieger): iterator that starts after some value (similar to next in hb).
64    // TODO(garretrieger): reverse iterator.
65
66    /// Iterator over the members of this page.
67    pub(crate) fn iter(&self) -> impl DoubleEndedIterator<Item = u32> + '_ {
68        self.storage
69            .iter()
70            .enumerate()
71            .filter(|(_, elem)| **elem != 0)
72            .flat_map(|(i, elem)| {
73                let base = i as u32 * ELEM_BITS;
74                Iter::new(*elem).map(move |idx| base + idx)
75            })
76    }
77
78    /// Iterator over the members of this page starting from value.
79    ///
80    /// So value is included in the iterator if it's in the page.
81    pub(crate) fn iter_from(&self, value: u32) -> impl DoubleEndedIterator<Item = u32> + '_ {
82        let start_index = Self::element_index(value);
83        self.storage[start_index..]
84            .iter()
85            .enumerate()
86            .filter(|(_, elem)| **elem != 0)
87            .flat_map(move |(i, elem)| {
88                let i = i + start_index;
89                let base = i as u32 * ELEM_BITS;
90                let it = if start_index == i {
91                    let index_in_elem = value & ELEM_MASK;
92                    Iter::from(*elem, index_in_elem)
93                } else {
94                    Iter::new(*elem)
95                };
96                it.map(move |idx| base + idx)
97            })
98    }
99
100    /// Iterator over the ranges in this page.
101    pub(crate) fn iter_ranges(&self) -> RangeIter<'_> {
102        RangeIter {
103            page: self,
104            next_value_to_check: 0,
105        }
106    }
107
108    /// Marks `(val % page width)` a member of this set and returns `true` if it is newly added.
109    pub(crate) fn insert(&mut self, val: u32) -> bool {
110        let el_mut = self.element_mut(val);
111        let mask = elem_index_bit_mask(val);
112        let is_new = (*el_mut & mask) == 0;
113        *el_mut |= mask;
114        self.length += is_new as u32;
115        is_new
116    }
117
118    /// Marks all values `[first, last]` as members of this set.
119    pub(crate) fn insert_range(&mut self, first: u32, last: u32) {
120        let first = first & PAGE_MASK;
121        let last = last & PAGE_MASK;
122        let first_elem_idx = first / ELEM_BITS;
123        let last_elem_idx = last / ELEM_BITS;
124
125        for elem_idx in first_elem_idx..=last_elem_idx {
126            let elem_start = first.max(elem_idx * ELEM_BITS) & ELEM_MASK;
127            let elem_last = last.min(((elem_idx + 1) * ELEM_BITS) - 1) & ELEM_MASK;
128
129            let end_shift = ELEM_BITS - elem_last - 1;
130            let mask = u64::MAX << (elem_start + end_shift);
131            let mask = mask >> end_shift;
132
133            self.storage[elem_idx as usize] |= mask;
134        }
135
136        self.recompute_length();
137    }
138
139    /// Marks all values `[first, last]` as not members of this set.
140    pub(crate) fn remove_range(&mut self, first: u32, last: u32) {
141        let first = first & PAGE_MASK;
142        let last = last & PAGE_MASK;
143        let first_elem_idx = first / ELEM_BITS;
144        let last_elem_idx = last / ELEM_BITS;
145
146        for elem_idx in first_elem_idx..=last_elem_idx {
147            let elem_start = first.max(elem_idx * ELEM_BITS) & ELEM_MASK;
148            let elem_last = last.min(((elem_idx + 1) * ELEM_BITS) - 1) & ELEM_MASK;
149
150            let end_shift = ELEM_BITS - elem_last - 1;
151            let mask = u64::MAX << (elem_start + end_shift);
152            let mask = !(mask >> end_shift);
153
154            self.storage[elem_idx as usize] &= mask;
155        }
156
157        self.recompute_length();
158    }
159
160    pub(crate) fn clear(&mut self) {
161        for elem in self.storage.iter_mut() {
162            *elem = 0;
163        }
164        self.length = 0;
165    }
166
167    /// Removes `(val % page width)` from this set.
168    pub(crate) fn remove(&mut self, val: u32) -> bool {
169        let ret = self.contains(val);
170        *self.element_mut(val) &= !elem_index_bit_mask(val);
171        self.length -= ret as u32;
172        ret
173    }
174
175    /// Return true if `(val % page width)` is a member of this set.
176    pub(crate) fn contains(&self, val: u32) -> bool {
177        (*self.element(val) & elem_index_bit_mask(val)) != 0
178    }
179
180    pub(crate) fn union(a: &BitPage, b: &BitPage) -> BitPage {
181        a.process(b, |a, b| a | b)
182    }
183
184    pub(crate) fn intersect(a: &BitPage, b: &BitPage) -> BitPage {
185        a.process(b, |a, b| a & b)
186    }
187
188    pub(crate) fn subtract(a: &BitPage, b: &BitPage) -> BitPage {
189        a.process(b, |a, b| a & !b)
190    }
191
192    fn process<Op>(&self, other: &BitPage, op: Op) -> BitPage
193    where
194        Op: Fn(Element, Element) -> Element,
195    {
196        let mut out = BitPage::new_zeroes();
197        for i in 0usize..(PAGE_SIZE as usize) {
198            out.storage[i] = op(self.storage[i], other.storage[i]);
199        }
200        out.recompute_length();
201        out
202    }
203
204    fn element(&self, value: u32) -> &Element {
205        &self.storage[Self::element_index(value)]
206    }
207
208    fn element_mut(&mut self, value: u32) -> &mut Element {
209        &mut self.storage[Self::element_index(value)]
210    }
211
212    const fn element_index(value: u32) -> usize {
213        (value as usize & PAGE_MASK as usize) / (ELEM_BITS as usize)
214    }
215}
216
217/// returns the bit to set in an element for this value
218const fn elem_index_bit_mask(value: u32) -> Element {
219    1 << (value & ELEM_MASK)
220}
221
222struct Iter {
223    val: Element,
224    forward_index: i32,
225    backward_index: i32,
226}
227
228impl Iter {
229    fn new(elem: Element) -> Iter {
230        Iter {
231            val: elem,
232            forward_index: 0,
233            backward_index: ELEM_BITS as i32 - 1,
234        }
235    }
236
237    /// Construct an iterator that starts at `index`
238    ///
239    /// Specifically if `index` bit is set it will be returned on the first call to `next()`.
240    fn from(elem: Element, index: u32) -> Iter {
241        Iter {
242            val: elem,
243            forward_index: index as i32, // index is at most 63
244            backward_index: ELEM_BITS as i32 - 1,
245        }
246    }
247}
248
249impl Iterator for Iter {
250    type Item = u32;
251
252    fn next(&mut self) -> Option<Self::Item> {
253        if self.forward_index > self.backward_index {
254            return None;
255        }
256        let mask = (1u64 << self.forward_index) - 1;
257        let masked = self.val & !mask;
258        let next_index = masked.trailing_zeros() as i32;
259        if next_index > self.backward_index {
260            return None;
261        }
262        self.forward_index = next_index + 1;
263        Some(next_index as u32)
264    }
265}
266
267impl DoubleEndedIterator for Iter {
268    fn next_back(&mut self) -> Option<Self::Item> {
269        if self.backward_index < self.forward_index {
270            return None;
271        }
272
273        let mask = 1u64
274            .checked_shl(self.backward_index as u32 + 1)
275            .map(|v| v - 1)
276            .unwrap_or(Element::MAX);
277        let masked = self.val & mask;
278        let next_index = (ELEM_BITS as i32) - (masked.leading_zeros() as i32) - 1;
279        if next_index < self.forward_index {
280            return None;
281        }
282        self.backward_index = next_index - 1;
283        Some(next_index as u32)
284    }
285}
286
287pub(crate) struct RangeIter<'a> {
288    page: &'a BitPage,
289    next_value_to_check: u32,
290}
291
292impl RangeIter<'_> {
293    fn next_range_in_element(&self) -> Option<RangeInclusive<u32>> {
294        if self.next_value_to_check >= PAGE_BITS {
295            return None;
296        }
297
298        let element = self.page.element(self.next_value_to_check);
299        let element_bit = (self.next_value_to_check & ELEM_MASK) as u64;
300        let major = self.next_value_to_check & !ELEM_MASK;
301
302        let mask = !((1 << element_bit) - 1);
303        let range_start = (element & mask).trailing_zeros();
304        if range_start == ELEM_BITS {
305            // There's no remaining values in this element.
306            return None;
307        }
308
309        let mask = (1 << range_start) - 1;
310        let range_end = (element | mask).trailing_ones() - 1;
311
312        Some((major + range_start)..=(major + range_end))
313    }
314}
315
316impl Iterator for RangeIter<'_> {
317    type Item = RangeInclusive<u32>;
318
319    fn next(&mut self) -> Option<Self::Item> {
320        let mut current_range = self.next_range_in_element();
321        loop {
322            let element_end = (self.next_value_to_check & !ELEM_MASK) + ELEM_BITS - 1;
323            let Some(range) = current_range.clone() else {
324                // No more ranges in the current element, move to the next one.
325                self.next_value_to_check = element_end + 1;
326                if self.next_value_to_check < PAGE_BITS {
327                    current_range = self.next_range_in_element();
328                    continue;
329                } else {
330                    return None;
331                }
332            };
333
334            self.next_value_to_check = range.end() + 1;
335            if *range.end() == element_end {
336                let continuation = self.next_range_in_element();
337                if let Some(continuation) = continuation {
338                    if *continuation.start() == element_end + 1 {
339                        current_range = Some(*range.start()..=*continuation.end());
340                        continue;
341                    }
342                }
343            }
344
345            break;
346        }
347
348        current_range
349    }
350}
351
352impl Default for BitPage {
353    fn default() -> Self {
354        Self::new_zeroes()
355    }
356}
357
358impl std::fmt::Debug for BitPage {
359    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
360        let values: Vec<_> = self.iter().collect();
361        std::fmt::Debug::fmt(&values, f)
362    }
363}
364
365impl Hash for BitPage {
366    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
367        self.storage.hash(state);
368    }
369}
370
371impl std::cmp::PartialEq for BitPage {
372    fn eq(&self, other: &Self) -> bool {
373        self.storage == other.storage
374    }
375}
376
377impl std::cmp::Eq for BitPage {}
378
379#[cfg(test)]
380mod test {
381    use std::collections::HashSet;
382
383    use super::*;
384
385    impl BitPage {
386        /// Create a new page with all bits set.
387        fn new_ones() -> Self {
388            Self {
389                storage: [Element::MAX; PAGE_SIZE as usize],
390                length: PAGE_SIZE * ELEM_BITS,
391            }
392        }
393    }
394
395    impl FromIterator<u32> for BitPage {
396        fn from_iter<I: IntoIterator<Item = u32>>(iter: I) -> Self {
397            let mut out = BitPage::new_zeroes();
398            for v in iter {
399                out.insert(v);
400            }
401            out
402        }
403    }
404
405    #[test]
406    fn test_iter_bit_indices() {
407        let items: Vec<_> = Iter::new(0).collect();
408        assert_eq!(items.len(), 0);
409
410        let items: Vec<_> = Iter::new(1).collect();
411        assert_eq!(items, vec![0]);
412
413        let items: Vec<_> = Iter::new(0b1100).collect();
414        assert_eq!(items, vec![2, 3]);
415
416        let items: Vec<_> = Iter::new(1 << 63).collect();
417        assert_eq!(items, vec![63]);
418
419        let items: Vec<_> = Iter::new((1 << 47) | (1 << 63)).collect();
420        assert_eq!(items, vec![47, 63]);
421
422        assert_eq!(Iter::new(Element::MAX).max(), Some(ELEM_BITS - 1));
423        assert_eq!(Iter::new(Element::MAX).min(), Some(0));
424    }
425
426    #[test]
427    fn test_iter_bit_indices_backwards() {
428        let mut it = Iter::new(0);
429        assert_eq!(None, it.next());
430        assert_eq!(None, it.next_back());
431
432        let mut it = Iter::new((1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6));
433        assert_eq!(Some(1), it.next());
434        assert_eq!(Some(6), it.next_back());
435        assert_eq!(Some(5), it.next_back());
436        assert_eq!(Some(2), it.next());
437        assert_eq!(Some(3), it.next());
438        assert_eq!(Some(4), it.next());
439        assert_eq!(None, it.next());
440        assert_eq!(None, it.next_back());
441
442        let mut it = Iter::new(1);
443        assert_eq!(Some(0), it.next_back());
444        assert_eq!(None, it.next_back());
445
446        let mut it = Iter::new(1 << 63);
447        assert_eq!(Some(63), it.next_back());
448        assert_eq!(None, it.next_back());
449
450        let mut it = Iter::new((1 << 63) | (1 << 62));
451        assert_eq!(Some(63), it.next_back());
452        assert_eq!(Some(62), it.next_back());
453        assert_eq!(None, it.next_back());
454
455        let mut it = Iter::new((1 << 63) | (1 << 32));
456        assert_eq!(Some(63), it.next_back());
457        assert_eq!(Some(32), it.next_back());
458        assert_eq!(None, it.next_back());
459    }
460
461    #[test]
462    fn page_init() {
463        let page = BitPage::new_zeroes();
464        assert_eq!(page.len(), 0);
465        assert!(page.is_empty());
466    }
467
468    #[test]
469    fn page_init_ones() {
470        let page = BitPage::new_ones();
471        assert_eq!(page.len(), 512);
472        assert!(!page.is_empty());
473    }
474
475    #[test]
476    fn page_contains_empty() {
477        let page = BitPage::new_zeroes();
478        assert!(!page.contains(0));
479        assert!(!page.contains(1));
480        assert!(!page.contains(75475));
481    }
482
483    #[test]
484    fn page_contains_all() {
485        let page = BitPage::new_ones();
486        assert!(page.contains(0));
487        assert!(page.contains(1));
488        assert!(page.contains(75475));
489    }
490
491    #[test]
492    fn page_insert() {
493        for val in 0..=1025 {
494            let mut page = BitPage::new_zeroes();
495            assert!(!page.contains(val), "unexpected {val} (1)");
496            page.insert(val);
497            assert!(page.contains(val), "missing {val}");
498            assert!(!page.contains(val.wrapping_sub(1)), "unexpected {val} (2)");
499        }
500    }
501
502    #[test]
503    fn page_insert_range() {
504        fn page_for_range(first: u32, last: u32) -> BitPage {
505            let mut page = BitPage::new_zeroes();
506            for i in first..=last {
507                page.insert(i);
508            }
509            page
510        }
511
512        for range in [
513            (0, 0),
514            (0, 1),
515            (1, 15),
516            (5, 63),
517            (64, 67),
518            (69, 72),
519            (69, 127),
520            (32, 345),
521            (512 + 32, 512 + 345),
522            (0, 511),
523        ] {
524            let mut page = BitPage::new_zeroes();
525            page.insert_range(range.0, range.1);
526            assert_eq!(page, page_for_range(range.0, range.1), "{range:?}");
527        }
528    }
529
530    #[test]
531    fn page_insert_return() {
532        let mut page = BitPage::new_zeroes();
533        assert!(page.insert(123));
534        assert!(!page.insert(123));
535    }
536
537    #[test]
538    fn page_remove() {
539        for val in 0..=1025 {
540            let mut page = BitPage::new_ones();
541            assert!(page.contains(val), "missing {val} (1)");
542            assert!(page.remove(val));
543            assert!(!page.remove(val));
544            assert!(!page.contains(val), "unexpected {val}");
545            assert!(page.contains(val.wrapping_sub(1)), "missing {val} (2)");
546        }
547    }
548
549    #[test]
550    fn page_remove_range() {
551        fn page_for_range(first: u32, last: u32) -> BitPage {
552            let mut page = BitPage::new_ones();
553            for i in first..=last {
554                page.remove(i);
555            }
556            page
557        }
558
559        for exclude_range in [
560            (0, 0),
561            (0, 1),
562            (1, 15),
563            (5, 63),
564            (64, 67),
565            (69, 72),
566            (69, 127),
567            (32, 345),
568            (0, 511),
569            (512 + 32, 512 + 345),
570        ] {
571            let mut page = BitPage::new_ones();
572            page.remove_range(exclude_range.0, exclude_range.1);
573            assert_eq!(
574                page,
575                page_for_range(exclude_range.0, exclude_range.1),
576                "{exclude_range:?}"
577            );
578        }
579    }
580
581    #[test]
582    fn clear() {
583        let mut zeroes = BitPage::new_zeroes();
584        let mut ones = BitPage::new_ones();
585
586        zeroes.clear();
587        assert_eq!(zeroes.len(), 0);
588        assert_eq!(zeroes.iter().next(), None);
589
590        zeroes.insert_range(10, 300);
591        zeroes.clear();
592        assert_eq!(zeroes.len(), 0);
593        assert_eq!(zeroes.iter().next(), None);
594
595        ones.clear();
596        assert_eq!(ones.len(), 0);
597        assert_eq!(ones.iter().next(), None);
598    }
599
600    #[test]
601    fn remove_to_empty_page() {
602        let mut page = BitPage::new_zeroes();
603
604        page.insert(13);
605        assert!(!page.is_empty());
606
607        page.remove(13);
608        assert!(page.is_empty());
609    }
610
611    #[test]
612    fn page_iter() {
613        let mut page = BitPage::new_zeroes();
614
615        page.insert(0);
616        page.insert(12);
617        page.insert(13);
618        page.insert(63);
619        page.insert(64);
620        page.insert(511);
621        page.insert(23);
622        page.insert(400);
623        page.insert(78);
624
625        let items: Vec<_> = page.iter().collect();
626        assert_eq!(items, vec![0, 12, 13, 23, 63, 64, 78, 400, 511,])
627    }
628
629    #[test]
630    fn page_iter_overflow() {
631        let mut page = BitPage::new_zeroes();
632        page.insert(0);
633        let mut it = page.iter();
634        assert_eq!(Some(0), it.next_back());
635        assert_eq!(None, it.next());
636    }
637
638    #[test]
639    fn page_iter_from() {
640        let mut page = BitPage::new_zeroes();
641        let items: Vec<_> = page.iter_from(0).collect();
642        assert!(items.is_empty());
643        let items: Vec<_> = page.iter_from(256).collect();
644        assert!(items.is_empty());
645
646        page.insert(1);
647        page.insert(12);
648        page.insert(13);
649        page.insert(63);
650        page.insert(64);
651        page.insert(511);
652        page.insert(23);
653        page.insert(400);
654        page.insert(78);
655
656        let items: Vec<_> = page.iter_from(0).collect();
657        assert_eq!(items, vec![1, 12, 13, 23, 63, 64, 78, 400, 511,]);
658
659        page.insert(0);
660        let items: Vec<_> = page.iter_from(0).collect();
661        assert_eq!(items, vec![0, 1, 12, 13, 23, 63, 64, 78, 400, 511,]);
662
663        let items: Vec<_> = page.iter_from(1).collect();
664        assert_eq!(items, vec![1, 12, 13, 23, 63, 64, 78, 400, 511,]);
665
666        let items: Vec<_> = page.iter_from(2).collect();
667        assert_eq!(items, vec![12, 13, 23, 63, 64, 78, 400, 511,]);
668
669        let items: Vec<_> = page.iter_from(63).collect();
670        assert_eq!(items, vec![63, 64, 78, 400, 511,]);
671
672        let items: Vec<_> = page.iter_from(256).collect();
673        assert_eq!(items, vec![400, 511]);
674
675        let items: Vec<_> = page.iter_from(511).collect();
676        assert_eq!(items, vec![511]);
677
678        let items: Vec<_> = page.iter_from(512).collect(); // page has 511 values, so 512 wraps around and acts like '0'
679        assert_eq!(items, vec![0, 1, 12, 13, 23, 63, 64, 78, 400, 511,]);
680
681        let items: Vec<_> = page.iter_from(515).collect(); // page has 511 values, so 515 wraps around and acts like '3'
682        assert_eq!(items, vec![12, 13, 23, 63, 64, 78, 400, 511,]);
683
684        let items: Vec<_> = page.iter_from(390).collect();
685        assert_eq!(items, vec![400, 511]);
686
687        let items: Vec<_> = page.iter_from(400).collect();
688        assert_eq!(items, vec![400, 511]);
689
690        let items: Vec<_> = page.iter_from(401).collect();
691        assert_eq!(items, vec![511]);
692    }
693
694    #[test]
695    fn page_iter_after_rev() {
696        let mut page = BitPage::new_zeroes();
697        let items: Vec<_> = page.iter_from(0).collect();
698        assert!(items.is_empty());
699        let items: Vec<_> = page.iter_from(256).collect();
700        assert!(items.is_empty());
701
702        page.insert(1);
703        page.insert(12);
704        page.insert(13);
705        page.insert(63);
706        page.insert(64);
707        page.insert(511);
708        page.insert(23);
709        page.insert(400);
710        page.insert(78);
711
712        let items: Vec<_> = page.iter_from(0).rev().collect();
713        assert_eq!(items, vec![511, 400, 78, 64, 63, 23, 13, 12, 1]);
714
715        page.insert(0);
716        let items: Vec<_> = page.iter_from(0).rev().collect();
717        assert_eq!(items, vec![511, 400, 78, 64, 63, 23, 13, 12, 1, 0]);
718
719        let items: Vec<_> = page.iter_from(1).rev().collect();
720        assert_eq!(items, vec![511, 400, 78, 64, 63, 23, 13, 12, 1]);
721
722        let items: Vec<_> = page.iter_from(63).rev().collect();
723        assert_eq!(items, vec![511, 400, 78, 64, 63]);
724
725        let items: Vec<_> = page.iter_from(256).rev().collect();
726        assert_eq!(items, vec![511, 400]);
727
728        let items: Vec<_> = page.iter_from(512).rev().collect();
729        assert_eq!(items, vec![511, 400, 78, 64, 63, 23, 13, 12, 1, 0]);
730
731        let items: Vec<_> = page.iter_from(390).rev().collect();
732        assert_eq!(items, vec![511, 400]);
733
734        let items: Vec<_> = page.iter_from(400).rev().collect();
735        assert_eq!(items, vec![511, 400]);
736
737        let items: Vec<_> = page.iter_from(401).rev().collect();
738        assert_eq!(items, vec![511]);
739    }
740
741    fn check_iter_ranges(ranges: Vec<RangeInclusive<u32>>) {
742        let mut page = BitPage::new_zeroes();
743        for range in ranges.iter() {
744            page.insert_range(*range.start(), *range.end());
745        }
746        let items: Vec<_> = page.iter_ranges().collect();
747        assert_eq!(items, ranges);
748    }
749
750    #[test]
751    fn iter_ranges() {
752        // basic
753        check_iter_ranges(vec![]);
754        check_iter_ranges(vec![0..=5]);
755        check_iter_ranges(vec![0..=0, 5..=5, 10..=10]);
756        check_iter_ranges(vec![0..=5, 12..=31]);
757        check_iter_ranges(vec![12..=31]);
758        check_iter_ranges(vec![71..=84]);
759        check_iter_ranges(vec![273..=284]);
760        check_iter_ranges(vec![0..=511]);
761
762        // end of boundary
763        check_iter_ranges(vec![511..=511]);
764        check_iter_ranges(vec![500..=511]);
765        check_iter_ranges(vec![400..=511]);
766        check_iter_ranges(vec![0..=511]);
767
768        // continuation ranges
769        check_iter_ranges(vec![64..=127]);
770        check_iter_ranges(vec![64..=127, 129..=135]);
771        check_iter_ranges(vec![64..=135]);
772        check_iter_ranges(vec![71..=135]);
773        check_iter_ranges(vec![71..=435]);
774    }
775
776    #[test]
777    fn union() {
778        let a = BitPage::new_zeroes();
779        let b = BitPage::from_iter([32, 400]);
780        let c = BitPage::from_iter([32, 200]);
781        let d = BitPage::from_iter([32, 200, 400]);
782
783        assert_eq!(BitPage::union(&a, &b), b);
784        assert_eq!(BitPage::union(&b, &a), b);
785        assert_eq!(BitPage::union(&b, &c), d);
786        assert_eq!(BitPage::union(&c, &b), d);
787    }
788
789    #[test]
790    fn intersect() {
791        let a = BitPage::new_zeroes();
792        let b = BitPage::from_iter([32, 400]);
793        let c = BitPage::from_iter([32, 200]);
794        let d = BitPage::from_iter([32]);
795
796        assert_eq!(BitPage::intersect(&a, &b), a);
797        assert_eq!(BitPage::intersect(&b, &a), a);
798        assert_eq!(BitPage::intersect(&b, &c), d);
799        assert_eq!(BitPage::intersect(&c, &b), d);
800    }
801
802    #[test]
803    fn subtract() {
804        let a = BitPage::new_zeroes();
805        let b = BitPage::from_iter([32, 400]);
806        let c = BitPage::from_iter([32, 200]);
807        let d = BitPage::from_iter([400]);
808        let e = BitPage::from_iter([200]);
809
810        assert_eq!(BitPage::subtract(&a, &b), a);
811        assert_eq!(BitPage::subtract(&b, &a), b);
812        assert_eq!(BitPage::subtract(&b, &c), d);
813        assert_eq!(BitPage::subtract(&c, &b), e);
814    }
815
816    #[test]
817    fn hash_and_eq() {
818        let mut page1 = BitPage::new_zeroes();
819        let mut page2 = BitPage::new_zeroes();
820        let mut page3 = BitPage::new_zeroes();
821
822        page1.insert(12);
823        page1.insert(300);
824
825        page2.insert(300);
826        page2.insert(12);
827        page2.len();
828
829        page3.insert(300);
830        page3.insert(12);
831        page3.insert(23);
832
833        assert_eq!(page1, page2);
834        assert_ne!(page1, page3);
835        assert_ne!(page2, page3);
836
837        let set = HashSet::from([page1]);
838        assert!(set.contains(&page2));
839        assert!(!set.contains(&page3));
840    }
841
842    #[test]
843    fn intersects() {
844        macro_rules! assert_intersects {
845            ($lhs:path, $rhs:path, $expected:expr) => {
846                assert_eq!($lhs.intersects_set(&$rhs), $expected);
847                assert_eq!($rhs.intersects_set(&$lhs), $expected);
848            };
849        }
850
851        let a = BitPage::new_zeroes();
852        let b = BitPage::from_iter([32, 400]);
853        let c = BitPage::from_iter([400]);
854        let d = BitPage::from_iter([401]);
855
856        assert_intersects!(a, b, false);
857        assert_intersects!(a, c, false);
858        assert_intersects!(a, d, false);
859
860        assert_intersects!(b, c, true);
861        assert_intersects!(b, d, false);
862
863        assert_intersects!(c, d, false);
864    }
865}
read_fonts/collections/int_set/bitpage.rs

read_fonts/collections/int_set/
bitpage.rs
