index/
bitmap.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::io;
16use std::ops::RangeInclusive;
17
18use common_base::BitVec;
19/// `BitmapType` enumerates how bitmaps are encoded within the inverted index.
20pub use greptime_proto::v1::index::BitmapType;
21use roaring::RoaringBitmap;
22
23/// A bitmap representation supporting both BitVec and RoaringBitmap formats.
24///
25/// This enum provides unified bitmap operations while allowing efficient storage
26/// in different formats. The implementation automatically handles type conversions
27/// when performing operations between different formats.
28///
29/// # Examples
30///
31/// Creating a new Roaring bitmap:
32/// ```
33/// use bitmap::Bitmap;
34/// let bitmap = Bitmap::new_roaring();
35/// assert!(bitmap.is_empty());
36/// ```
37///
38/// Creating a full BitVec bitmap:
39/// ```
40/// use bitmap::Bitmap;
41/// let bitmap = Bitmap::full_bitvec(10);
42/// assert_eq!(bitmap.count_ones(), 10);
43/// ```
44#[derive(Debug, Clone, PartialEq)]
45pub enum Bitmap {
46    Roaring(RoaringBitmap),
47    BitVec(BitVec),
48}
49
50impl Bitmap {
51    /// Creates a new empty BitVec-based bitmap.
52    pub fn new_bitvec() -> Self {
53        Bitmap::BitVec(BitVec::EMPTY)
54    }
55
56    /// Creates a new empty RoaringBitmap-based bitmap.
57    pub fn new_roaring() -> Self {
58        Bitmap::Roaring(RoaringBitmap::new())
59    }
60
61    /// Creates a full BitVec-based bitmap with all bits set to 1.
62    ///
63    /// # Arguments
64    /// * `size` - The number of bits to allocate and set
65    pub fn full_bitvec(size: usize) -> Self {
66        Bitmap::BitVec(BitVec::repeat(true, size))
67    }
68
69    /// Creates a full RoaringBitmap-based bitmap with bits 0..size set to 1.
70    ///
71    /// # Arguments
72    /// * `size` - The exclusive upper bound for the bit range
73    pub fn full_roaring(size: usize) -> Self {
74        let mut roaring = RoaringBitmap::new();
75        roaring.insert_range(0..size as u32);
76        Bitmap::Roaring(roaring)
77    }
78
79    /// Returns the number of bits set to 1 in the bitmap.
80    pub fn count_ones(&self) -> usize {
81        match self {
82            Bitmap::BitVec(bitvec) => bitvec.count_ones(),
83            Bitmap::Roaring(roaring) => roaring.len() as _,
84        }
85    }
86
87    /// Checks if the bitmap contains no set bits.
88    pub fn is_empty(&self) -> bool {
89        match self {
90            Bitmap::BitVec(bitvec) => bitvec.is_empty(),
91            Bitmap::Roaring(roaring) => roaring.is_empty(),
92        }
93    }
94
95    /// Inserts a range of bits into the bitmap.
96    ///
97    /// # Arguments
98    /// * `range` - Inclusive range of bits to set
99    pub fn insert_range(&mut self, range: RangeInclusive<usize>) {
100        match self {
101            Bitmap::BitVec(bitvec) => {
102                if *range.end() >= bitvec.len() {
103                    bitvec.resize(range.end() + 1, false);
104                }
105                for i in range {
106                    bitvec.set(i, true);
107                }
108            }
109            Bitmap::Roaring(roaring) => {
110                let range = *range.start() as u32..=*range.end() as u32;
111                roaring.insert_range(range);
112            }
113        }
114    }
115
116    /// Serializes the bitmap into a byte buffer using the specified format.
117    ///
118    /// # Arguments
119    /// * `serialize_type` - Target format for serialization
120    /// * `writer` - Output writer to write the serialized data
121    pub fn serialize_into(
122        &self,
123        serialize_type: BitmapType,
124        mut writer: impl io::Write,
125    ) -> io::Result<()> {
126        match (self, serialize_type) {
127            (Bitmap::BitVec(bitvec), BitmapType::BitVec) => {
128                writer.write_all(bitvec.as_raw_slice())?;
129            }
130            (Bitmap::Roaring(roaring), BitmapType::Roaring) => {
131                roaring.serialize_into(writer)?;
132            }
133            (Bitmap::BitVec(bitvec), BitmapType::Roaring) => {
134                let bitmap = Bitmap::bitvec_to_roaring(bitvec.clone());
135                bitmap.serialize_into(writer)?;
136            }
137            (Bitmap::Roaring(roaring), BitmapType::BitVec) => {
138                let bitvec = Bitmap::roaring_to_bitvec(roaring);
139                writer.write_all(bitvec.as_raw_slice())?;
140            }
141        }
142
143        Ok(())
144    }
145
146    /// Computes the size of the serialized bitmap in bytes.
147    ///
148    /// # Arguments
149    /// * `bitmap_type` - Format of data to be serialized
150    pub fn serialized_size(&self, bitmap_type: BitmapType) -> usize {
151        match (self, bitmap_type) {
152            (Bitmap::BitVec(bitvec), BitmapType::BitVec) => bitvec.as_raw_slice().len(),
153            (Bitmap::Roaring(roaring), BitmapType::Roaring) => roaring.serialized_size(),
154            (Bitmap::BitVec(bitvec), BitmapType::Roaring) => {
155                let bitmap = Bitmap::bitvec_to_roaring(bitvec.clone());
156                bitmap.serialized_size()
157            }
158            (Bitmap::Roaring(roaring), BitmapType::BitVec) => {
159                let bitvec = Bitmap::roaring_to_bitvec(roaring);
160                bitvec.as_raw_slice().len()
161            }
162        }
163    }
164
165    /// Deserializes a bitmap from a byte buffer.
166    ///
167    /// # Arguments
168    /// * `buf` - Input buffer containing serialized data
169    /// * `bitmap_type` - Format of the serialized data
170    pub fn deserialize_from(buf: &[u8], bitmap_type: BitmapType) -> std::io::Result<Self> {
171        match bitmap_type {
172            BitmapType::BitVec => {
173                let bitvec = BitVec::from_slice(buf);
174                Ok(Bitmap::BitVec(bitvec))
175            }
176            BitmapType::Roaring => {
177                let roaring = RoaringBitmap::deserialize_from(buf)?;
178                Ok(Bitmap::Roaring(roaring))
179            }
180        }
181    }
182
183    /// Computes the union with another bitmap (in-place).
184    ///
185    /// If the other bitmap is a different type, it will be converted to match
186    /// the current bitmap's type.
187    pub fn union(&mut self, other: Self) {
188        if self.is_empty() {
189            *self = other;
190            return;
191        }
192
193        match (self, other) {
194            (Bitmap::BitVec(bitvec1), bitmap) => {
195                let bitvec2 = bitmap.into_bitvec();
196                if bitvec1.len() > bitvec2.len() {
197                    *bitvec1 |= bitvec2
198                } else {
199                    *bitvec1 = bitvec2 | &*bitvec1;
200                }
201            }
202            (Bitmap::Roaring(roaring1), bitmap) => {
203                let roaring2 = bitmap.into_roaring();
204                *roaring1 |= roaring2;
205            }
206        }
207    }
208
209    /// Computes the intersection with another bitmap (in-place).
210    ///
211    /// If the other bitmap is a different type, it will be converted to match
212    /// the current bitmap's type.
213    pub fn intersect(&mut self, other: Self) {
214        match (self, other) {
215            (Bitmap::BitVec(bitvec1), bitmap) => {
216                let mut bitvec2 = bitmap.into_bitvec();
217                let len = (bitvec1.len() - bitvec1.trailing_zeros())
218                    .min(bitvec2.len() - bitvec2.trailing_zeros());
219                bitvec1.truncate(len);
220                bitvec2.truncate(len);
221                *bitvec1 &= bitvec2;
222            }
223            (Bitmap::Roaring(roaring1), bitmap) => {
224                let roaring2 = bitmap.into_roaring();
225                *roaring1 &= roaring2;
226            }
227        }
228    }
229
230    /// Returns an iterator over the indices of set bits.
231    pub fn iter_ones(&self) -> Box<dyn Iterator<Item = usize> + '_> {
232        match self {
233            Bitmap::BitVec(bitvec) => Box::new(bitvec.iter_ones()),
234            Bitmap::Roaring(roaring) => Box::new(roaring.iter().map(|x| x as usize)),
235        }
236    }
237
238    /// Creates a bitmap from bytes in LSB0 (least significant bit first) order.
239    ///
240    /// # Arguments
241    /// * `bytes` - Input bytes in LSB0 order
242    /// * `bitmap_type` - Type of bitmap to create
243    pub fn from_lsb0_bytes(bytes: &[u8], bitmap_type: BitmapType) -> Self {
244        match bitmap_type {
245            BitmapType::BitVec => {
246                let bitvec = BitVec::from_slice(bytes);
247                Bitmap::BitVec(bitvec)
248            }
249            BitmapType::Roaring => {
250                let roaring = RoaringBitmap::from_lsb0_bytes(0, bytes);
251                Bitmap::Roaring(roaring)
252            }
253        }
254    }
255
256    /// Computes memory usage of the bitmap in bytes.
257    pub fn memory_usage(&self) -> usize {
258        match self {
259            Bitmap::BitVec(bitvec) => bitvec.capacity(),
260            Bitmap::Roaring(roaring) => {
261                let stat = roaring.statistics();
262                (stat.n_bytes_array_containers
263                    + stat.n_bytes_bitset_containers
264                    + stat.n_bytes_run_containers) as usize
265            }
266        }
267    }
268
269    fn into_bitvec(self) -> BitVec {
270        match self {
271            Bitmap::BitVec(bitvec) => bitvec,
272            Bitmap::Roaring(roaring) => Self::roaring_to_bitvec(&roaring),
273        }
274    }
275
276    fn into_roaring(self) -> RoaringBitmap {
277        match self {
278            Bitmap::Roaring(roaring) => roaring,
279            Bitmap::BitVec(bitvec) => Self::bitvec_to_roaring(bitvec),
280        }
281    }
282
283    fn roaring_to_bitvec(roaring: &RoaringBitmap) -> BitVec {
284        let max_value = roaring.max().unwrap_or(0);
285        let mut bitvec = BitVec::repeat(false, max_value as usize + 1);
286        for i in roaring {
287            bitvec.set(i as usize, true);
288        }
289        bitvec
290    }
291
292    fn bitvec_to_roaring(mut bitvec: BitVec) -> RoaringBitmap {
293        bitvec.resize(bitvec.capacity(), false);
294        RoaringBitmap::from_lsb0_bytes(0, bitvec.as_raw_slice())
295    }
296}
297
298impl Default for Bitmap {
299    fn default() -> Self {
300        Bitmap::new_roaring()
301    }
302}
303
304#[cfg(test)]
305mod tests {
306    use super::*;
307
308    #[test]
309    fn test_full_bitmaps() {
310        let bv = Bitmap::full_bitvec(10);
311        assert_eq!(bv.count_ones(), 10);
312
313        let rb = Bitmap::full_roaring(10);
314        assert_eq!(rb.count_ones(), 10);
315    }
316
317    #[test]
318    fn test_serialization_roundtrip() {
319        let original = Bitmap::full_roaring(100);
320        let mut buf = Vec::new();
321
322        // Serialize as Roaring
323        original
324            .serialize_into(BitmapType::Roaring, &mut buf)
325            .unwrap();
326        let deserialized = Bitmap::deserialize_from(&buf, BitmapType::Roaring).unwrap();
327        assert_eq!(original, deserialized);
328
329        // Serialize as BitVec
330        buf.clear();
331        original
332            .serialize_into(BitmapType::BitVec, &mut buf)
333            .unwrap();
334        let deserialized = Bitmap::deserialize_from(&buf, BitmapType::BitVec).unwrap();
335        assert_eq!(original.count_ones(), deserialized.count_ones());
336    }
337
338    #[test]
339    fn test_union_fulls() {
340        // Test BitVec union
341        let mut bv1 = Bitmap::full_bitvec(3); // 0-2: 111
342        let bv2 = Bitmap::full_bitvec(5); // 0-4: 11111
343        bv1.union(bv2);
344        assert_eq!(bv1.count_ones(), 5);
345
346        let mut bv1 = Bitmap::full_bitvec(5); // 0-4: 11111
347        let bv2 = Bitmap::full_bitvec(3); // 0-2: 111
348        bv1.union(bv2);
349        assert_eq!(bv1.count_ones(), 5);
350
351        // Test Roaring union
352        let mut rb1 = Bitmap::full_roaring(3); // 0-2: 111
353        let rb2 = Bitmap::full_roaring(5); // 0-4: 11111
354        rb1.union(rb2);
355        assert_eq!(rb1.count_ones(), 5);
356
357        let mut rb1 = Bitmap::full_roaring(5); // 0-4: 11111
358        let rb2 = Bitmap::full_roaring(3); // 0-2: 111
359        rb1.union(rb2);
360        assert_eq!(rb1.count_ones(), 5);
361
362        // Test cross-type union
363        let mut rb = Bitmap::full_roaring(5); // 0-4: 11111
364        let bv = Bitmap::full_bitvec(3); // 0-2: 111
365        rb.union(bv);
366        assert_eq!(rb.count_ones(), 5);
367
368        let mut bv = Bitmap::full_bitvec(5); // 0-4: 11111
369        let rb = Bitmap::full_roaring(3); // 0-2: 111
370        bv.union(rb);
371        assert_eq!(bv.count_ones(), 5);
372
373        let mut rb = Bitmap::full_roaring(3); // 0-2: 111
374        let bv = Bitmap::full_bitvec(5); // 0-4: 11111
375        rb.union(bv);
376        assert_eq!(rb.count_ones(), 5);
377
378        let mut bv = Bitmap::full_bitvec(3); // 0-2: 111
379        let rb = Bitmap::full_roaring(5); // 0-4: 11111
380        bv.union(rb);
381        assert_eq!(bv.count_ones(), 5);
382    }
383
384    #[test]
385    fn test_union_bitvec() {
386        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
387        let bv2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
388        bv1.union(bv2);
389        assert_eq!(
390            bv1,
391            Bitmap::from_lsb0_bytes(&[0b11111111], BitmapType::BitVec)
392        );
393
394        // Test different lengths
395        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
396        let bv2 = Bitmap::from_lsb0_bytes(&[0b01010101, 0b00000001], BitmapType::BitVec);
397        bv1.union(bv2);
398        assert_eq!(
399            bv1,
400            Bitmap::from_lsb0_bytes(&[0b11111111, 0b00000001], BitmapType::BitVec)
401        );
402
403        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::BitVec);
404        let bv2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
405        bv1.union(bv2);
406        assert_eq!(
407            bv1,
408            Bitmap::from_lsb0_bytes(&[0b11111111, 0b00000001], BitmapType::BitVec)
409        );
410
411        // Test empty bitmaps
412        let mut bv1 = Bitmap::new_bitvec();
413        let bv2 = Bitmap::new_bitvec();
414        bv1.union(bv2);
415        assert!(bv1.is_empty());
416
417        let mut bv1 = Bitmap::new_bitvec();
418        let bv2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
419        bv1.union(bv2);
420        assert_eq!(
421            bv1,
422            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec)
423        );
424
425        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
426        let bv2 = Bitmap::new_bitvec();
427        bv1.union(bv2);
428        assert_eq!(
429            bv1,
430            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec)
431        );
432
433        // Test empty and full bitmaps
434        let mut bv1 = Bitmap::new_bitvec();
435        let bv2 = Bitmap::full_bitvec(8);
436        bv1.union(bv2);
437        assert_eq!(bv1, Bitmap::full_bitvec(8));
438
439        let mut bv1 = Bitmap::full_bitvec(8);
440        let bv2 = Bitmap::new_bitvec();
441        bv1.union(bv2);
442        assert_eq!(bv1, Bitmap::full_bitvec(8));
443    }
444
445    #[test]
446    fn test_union_roaring() {
447        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
448        let rb2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
449        rb1.union(rb2);
450        assert_eq!(
451            rb1,
452            Bitmap::from_lsb0_bytes(&[0b11111111], BitmapType::Roaring)
453        );
454
455        // Test different lengths
456        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
457        let rb2 = Bitmap::from_lsb0_bytes(&[0b01010101, 0b00000001], BitmapType::Roaring);
458        rb1.union(rb2);
459        assert_eq!(
460            rb1,
461            Bitmap::from_lsb0_bytes(&[0b11111111, 0b00000001], BitmapType::Roaring)
462        );
463
464        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::Roaring);
465        let rb2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
466        rb1.union(rb2);
467        assert_eq!(
468            rb1,
469            Bitmap::from_lsb0_bytes(&[0b11111111, 0b00000001], BitmapType::Roaring)
470        );
471
472        // Test empty bitmaps
473        let mut rb1 = Bitmap::new_roaring();
474        let rb2 = Bitmap::new_roaring();
475        rb1.union(rb2);
476        assert!(rb1.is_empty());
477
478        let mut rb1 = Bitmap::new_roaring();
479        let rb2 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
480        rb1.union(rb2);
481        assert_eq!(
482            rb1,
483            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring)
484        );
485
486        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
487        let rb2 = Bitmap::new_roaring();
488        rb1.union(rb2);
489        assert_eq!(
490            rb1,
491            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring)
492        );
493
494        // Test empty and full bit
495        let mut rb1 = Bitmap::new_roaring();
496        let rb2 = Bitmap::full_roaring(8);
497        rb1.union(rb2);
498        assert_eq!(rb1, Bitmap::full_roaring(8));
499
500        let mut rb1 = Bitmap::full_roaring(8);
501        let rb2 = Bitmap::new_roaring();
502        rb1.union(rb2);
503        assert_eq!(rb1, Bitmap::full_roaring(8));
504    }
505
506    #[test]
507    fn test_union_mixed() {
508        let mut rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
509        let bv = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
510        rb.union(bv);
511        assert_eq!(
512            rb,
513            Bitmap::from_lsb0_bytes(&[0b11111111], BitmapType::Roaring)
514        );
515
516        let mut bv = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
517        let rb = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
518        bv.union(rb);
519        assert_eq!(
520            bv,
521            Bitmap::from_lsb0_bytes(&[0b11111111], BitmapType::BitVec)
522        );
523
524        let mut rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
525        let bv = Bitmap::full_bitvec(8);
526        rb.union(bv);
527        assert_eq!(rb, Bitmap::full_roaring(8));
528
529        let mut bv = Bitmap::full_bitvec(8);
530        let rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
531        bv.union(rb);
532        assert_eq!(bv, Bitmap::full_bitvec(8));
533
534        let mut rb = Bitmap::new_roaring();
535        let bv = Bitmap::full_bitvec(8);
536        rb.union(bv);
537        assert_eq!(rb, Bitmap::full_bitvec(8));
538
539        let mut bv = Bitmap::full_bitvec(8);
540        let rb = Bitmap::new_roaring();
541        bv.union(rb);
542        assert_eq!(bv, Bitmap::full_bitvec(8));
543
544        let mut rb = Bitmap::new_roaring();
545        let bv = Bitmap::new_bitvec();
546        rb.union(bv);
547        assert!(rb.is_empty());
548
549        let mut bv = Bitmap::new_bitvec();
550        let rb = Bitmap::new_roaring();
551        bv.union(rb);
552        assert!(bv.is_empty());
553
554        let mut rb = Bitmap::new_roaring();
555        let bv = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
556        rb.union(bv);
557        assert_eq!(
558            rb,
559            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec)
560        );
561
562        let mut bv = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec);
563        let rb = Bitmap::new_roaring();
564        bv.union(rb);
565        assert_eq!(
566            bv,
567            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::BitVec)
568        );
569
570        let mut rb = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
571        let bv = Bitmap::new_bitvec();
572        rb.union(bv);
573        assert_eq!(
574            rb,
575            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring)
576        );
577
578        let mut bv = Bitmap::new_bitvec();
579        let rb = Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring);
580        bv.union(rb);
581        assert_eq!(
582            bv,
583            Bitmap::from_lsb0_bytes(&[0b01010101], BitmapType::Roaring)
584        );
585    }
586
587    #[test]
588    fn test_intersect_fulls() {
589        // Test BitVec intersect
590        let mut bv1 = Bitmap::full_bitvec(3); // 0-2: 111
591        let bv2 = Bitmap::full_bitvec(5); // 0-4: 11111
592        bv1.intersect(bv2);
593        assert_eq!(bv1.count_ones(), 3);
594
595        let mut bv1 = Bitmap::full_bitvec(5); // 0-4: 11111
596        let bv2 = Bitmap::full_bitvec(3); // 0-2: 111
597        bv1.intersect(bv2);
598        assert_eq!(bv1.count_ones(), 3);
599
600        // Test Roaring intersect
601        let mut rb1 = Bitmap::full_roaring(3); // 0-2: 111
602        let rb2 = Bitmap::full_roaring(5); // 0-4: 11111
603        rb1.intersect(rb2);
604        assert_eq!(rb1.count_ones(), 3);
605
606        let mut rb1 = Bitmap::full_roaring(5); // 0-4: 11111
607        let rb2 = Bitmap::full_roaring(3); // 0-2: 111
608        rb1.intersect(rb2);
609        assert_eq!(rb1.count_ones(), 3);
610
611        // Test cross-type intersect
612        let mut rb = Bitmap::full_roaring(5); // 0-4: 11111
613        let bv = Bitmap::full_bitvec(3); // 0-2: 111
614        rb.intersect(bv);
615        assert_eq!(rb.count_ones(), 3);
616
617        let mut bv = Bitmap::full_bitvec(5); // 0-4: 11111
618        let rb = Bitmap::full_roaring(3); // 0-2: 111
619        bv.intersect(rb);
620        assert_eq!(bv.count_ones(), 3);
621
622        let mut rb = Bitmap::full_roaring(3); // 0-2: 111
623        let bv = Bitmap::full_bitvec(5); // 0-4: 11111
624        rb.intersect(bv);
625        assert_eq!(rb.count_ones(), 3);
626
627        let mut bv = Bitmap::full_bitvec(3); // 0-2: 111
628        let rb = Bitmap::full_roaring(5); // 0-4: 11111
629        bv.intersect(rb);
630        assert_eq!(bv.count_ones(), 3);
631    }
632
633    #[test]
634    fn test_intersect_bitvec() {
635        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::BitVec);
636        let bv2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
637        bv1.intersect(bv2);
638        assert_eq!(
639            bv1,
640            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
641        );
642
643        // Test different lengths
644        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::BitVec);
645        let bv2 = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::BitVec);
646        bv1.intersect(bv2);
647        assert_eq!(
648            bv1,
649            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
650        );
651
652        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b11110000, 0b00000001], BitmapType::BitVec);
653        let bv2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
654        bv1.intersect(bv2);
655        assert_eq!(
656            bv1,
657            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
658        );
659
660        // Test empty bitmaps
661        let mut bv1 = Bitmap::new_bitvec();
662        let bv2 = Bitmap::new_bitvec();
663        bv1.intersect(bv2);
664        assert!(bv1.is_empty());
665
666        let mut bv1 = Bitmap::new_bitvec();
667        let bv2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
668        bv1.intersect(bv2);
669        assert!(bv1.is_empty());
670
671        let mut bv1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
672        let bv2 = Bitmap::new_bitvec();
673        bv1.intersect(bv2);
674        assert!(bv1.is_empty());
675
676        // Test empty and full bitmaps
677        let mut bv1 = Bitmap::new_bitvec();
678        let bv2 = Bitmap::full_bitvec(8);
679        bv1.intersect(bv2);
680        assert!(bv1.is_empty());
681
682        let mut bv1 = Bitmap::full_bitvec(8);
683        let bv2 = Bitmap::new_bitvec();
684        bv1.intersect(bv2);
685        assert!(bv1.is_empty());
686    }
687
688    #[test]
689    fn test_intersect_roaring() {
690        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
691        let rb2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
692        rb1.intersect(rb2);
693        assert_eq!(
694            rb1,
695            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
696        );
697
698        // Test different lengths
699        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
700        let rb2 = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::Roaring);
701        rb1.intersect(rb2);
702        assert_eq!(
703            rb1,
704            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
705        );
706
707        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b11110000, 0b00000001], BitmapType::Roaring);
708        let rb2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
709        rb1.intersect(rb2);
710        assert_eq!(
711            rb1,
712            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
713        );
714
715        // Test empty bitmaps
716        let mut rb1 = Bitmap::new_roaring();
717        let rb2 = Bitmap::new_roaring();
718        rb1.intersect(rb2);
719        assert!(rb1.is_empty());
720
721        let mut rb1 = Bitmap::new_roaring();
722        let rb2 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
723        rb1.intersect(rb2);
724        assert!(rb1.is_empty());
725
726        let mut rb1 = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
727        let rb2 = Bitmap::new_roaring();
728        rb1.intersect(rb2);
729        assert!(rb1.is_empty());
730
731        // Test empty and full bitmaps
732        let mut rb1 = Bitmap::new_roaring();
733        let rb2 = Bitmap::full_roaring(8);
734        rb1.intersect(rb2);
735        assert!(rb1.is_empty());
736
737        let mut rb1 = Bitmap::full_roaring(8);
738        let rb2 = Bitmap::new_roaring();
739        rb1.intersect(rb2);
740        assert!(rb1.is_empty());
741    }
742
743    #[test]
744    fn test_intersect_mixed() {
745        let mut rb = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
746        let bv = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
747        rb.intersect(bv);
748        assert_eq!(
749            rb,
750            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
751        );
752
753        let mut bv = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::BitVec);
754        let rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
755        bv.intersect(rb);
756        assert_eq!(
757            bv,
758            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
759        );
760
761        let mut rb = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
762        let bv = Bitmap::full_bitvec(8);
763        rb.intersect(bv);
764        assert_eq!(
765            rb,
766            Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring)
767        );
768
769        let mut bv = Bitmap::full_bitvec(8);
770        let rb = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
771        bv.intersect(rb);
772        assert_eq!(
773            bv,
774            Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::BitVec)
775        );
776
777        let mut rb = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::Roaring);
778        let bv = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::BitVec);
779        rb.intersect(bv);
780        assert_eq!(
781            rb,
782            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
783        );
784
785        let mut bv = Bitmap::from_lsb0_bytes(&[0b11110000, 0b00000001], BitmapType::BitVec);
786        let rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
787        bv.intersect(rb);
788        assert_eq!(
789            bv,
790            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
791        );
792
793        let mut rb = Bitmap::from_lsb0_bytes(&[0b11110000, 0b00000001], BitmapType::Roaring);
794        let bv = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
795        rb.intersect(bv);
796        assert_eq!(
797            rb,
798            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::Roaring)
799        );
800
801        let mut bv = Bitmap::from_lsb0_bytes(&[0b11110000], BitmapType::BitVec);
802        let rb = Bitmap::from_lsb0_bytes(&[0b10101010, 0b00000001], BitmapType::Roaring);
803        bv.intersect(rb);
804        assert_eq!(
805            bv,
806            Bitmap::from_lsb0_bytes(&[0b10100000], BitmapType::BitVec)
807        );
808
809        let mut rb = Bitmap::new_roaring();
810        let bv = Bitmap::full_bitvec(8);
811        rb.intersect(bv);
812        assert!(rb.is_empty());
813
814        let mut bv = Bitmap::full_bitvec(8);
815        let rb = Bitmap::new_roaring();
816        bv.intersect(rb);
817        assert!(bv.is_empty());
818
819        let mut bv = Bitmap::new_bitvec();
820        let rb = Bitmap::full_roaring(8);
821        bv.intersect(rb);
822        assert!(bv.is_empty());
823
824        let mut rb = Bitmap::full_roaring(8);
825        let bv = Bitmap::new_bitvec();
826        rb.intersect(bv);
827        assert!(rb.is_empty());
828
829        let mut rb = Bitmap::new_roaring();
830        let bv = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
831        rb.intersect(bv);
832        assert!(rb.is_empty());
833
834        let mut bv = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::BitVec);
835        let rb = Bitmap::new_roaring();
836        bv.intersect(rb);
837        assert!(bv.is_empty());
838
839        let mut bv = Bitmap::new_bitvec();
840        let rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
841        bv.intersect(rb);
842        assert!(bv.is_empty());
843
844        let mut rb = Bitmap::from_lsb0_bytes(&[0b10101010], BitmapType::Roaring);
845        let bv = Bitmap::new_bitvec();
846        rb.intersect(bv);
847        assert!(rb.is_empty());
848    }
849
850    #[test]
851    fn test_insert_range() {
852        let mut bv = Bitmap::new_bitvec();
853        bv.insert_range(0..=5);
854        assert_eq!(bv.iter_ones().collect::<Vec<_>>(), vec![0, 1, 2, 3, 4, 5]);
855
856        let mut rb = Bitmap::new_roaring();
857        rb.insert_range(0..=5);
858        assert_eq!(bv.iter_ones().collect::<Vec<_>>(), vec![0, 1, 2, 3, 4, 5]);
859
860        let mut bv = Bitmap::new_bitvec();
861        bv.insert_range(10..=10);
862        assert_eq!(bv.iter_ones().collect::<Vec<_>>(), vec![10]);
863
864        let mut rb = Bitmap::new_roaring();
865        rb.insert_range(10..=10);
866        assert_eq!(bv.iter_ones().collect::<Vec<_>>(), vec![10]);
867    }
868}
index/bitmap.rs

index/
bitmap.rs
