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

read_fonts/collections/int_set/
bitpage.rs
