read_fonts/collections/int_set/
bitpage.rs

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

read_fonts/collections/int_set/
bitpage.rs
