read_fonts/collections/int_set/
bitpage.rs

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

read_fonts/collections/int_set/
bitpage.rs
