croaring_mw/bitmap/imp.rs
1use std::ops::Range;
2
3use super::{ffi, Bitmap, Statistics};
4
5impl Bitmap {
6 /// Creates a new bitmap (initially empty)
7 ///
8 /// # Examples
9 ///
10 /// ```
11 /// use croaring::Bitmap;
12 ///
13 /// let bitmap = Bitmap::create();
14 ///
15 /// assert!(bitmap.is_empty());
16 /// ```
17 #[inline]
18 pub fn create() -> Self {
19 let bitmap = unsafe { ffi::roaring_bitmap_create() };
20
21 Bitmap { bitmap }
22 }
23
24 /// Creates a new bitmap (initially empty) with a provided
25 /// container-storage capacity (it is a performance hint).
26 ///
27 /// # Examples
28 ///
29 /// ```
30 /// use croaring::Bitmap;
31 ///
32 /// let bitmap = Bitmap::create_with_capacity(100_000);
33 ///
34 /// assert!(bitmap.is_empty());
35 /// ```
36 #[inline]
37 pub fn create_with_capacity(capacity: u32) -> Self {
38 let bitmap = unsafe { ffi::roaring_bitmap_create_with_capacity(capacity) };
39
40 Bitmap { bitmap }
41 }
42
43 /// Add the integer element to the bitmap
44 ///
45 /// # Examples
46 ///
47 /// ```
48 /// use croaring::Bitmap;
49 ///
50 /// let mut bitmap = Bitmap::create();
51 /// bitmap.add_many(&[1, 2, 3]);
52 ///
53 /// assert!(!bitmap.is_empty());
54 /// assert!(bitmap.contains(1));
55 /// assert!(bitmap.contains(2));
56 /// assert!(bitmap.contains(3));
57 /// ```
58 #[inline]
59 pub fn add_many(&mut self, elements: &[u32]) {
60 unsafe { ffi::roaring_bitmap_add_many(self.bitmap, elements.len(), elements.as_ptr()) }
61 }
62
63 /// Add the integer element to the bitmap
64 ///
65 /// # Examples
66 ///
67 /// ```
68 /// use croaring::Bitmap;
69 ///
70 /// let mut bitmap = Bitmap::create();
71 /// bitmap.add(1);
72 ///
73 /// assert!(!bitmap.is_empty());
74 /// ```
75 #[inline]
76 pub fn add(&mut self, element: u32) {
77 unsafe { ffi::roaring_bitmap_add(self.bitmap, element) }
78 }
79
80 /// Add the integer element to the bitmap. Returns true if the value was
81 /// added, false if the value was already in the bitmap.
82 ///
83 /// # Examples
84 ///
85 /// ```
86 /// use croaring::Bitmap;
87 ///
88 /// let mut bitmap = Bitmap::create();
89 /// assert!(bitmap.add_checked(1));
90 /// assert!(!bitmap.add_checked(1));
91 /// ```
92 #[inline]
93 pub fn add_checked(&mut self, element: u32) -> bool {
94 unsafe { ffi::roaring_bitmap_add_checked(self.bitmap, element) }
95 }
96
97 /// Add all values in range [range_min, range_max)
98 ///
99 /// # Examples
100 ///
101 /// ```
102 /// use croaring::Bitmap;
103 ///
104 /// let mut bitmap1 = Bitmap::create();
105 /// bitmap1.add_range((1..3));
106 ///
107 /// assert!(!bitmap1.is_empty());
108 /// assert!(bitmap1.contains(1));
109 /// assert!(bitmap1.contains(2));
110 /// assert!(!bitmap1.contains(3));
111 ///
112 /// let mut bitmap2 = Bitmap::create();
113 /// bitmap2.add_range((3..1));
114 /// assert!(bitmap2.is_empty());
115 ///
116 /// let mut bitmap3 = Bitmap::create();
117 /// bitmap3.add_range((3..3));
118 /// assert!(bitmap3.is_empty());
119 /// ```
120 #[inline]
121 pub fn add_range(&mut self, range: Range<u64>) {
122 unsafe { ffi::roaring_bitmap_add_range(self.bitmap, range.start, range.end) }
123 }
124
125 /// Remove all values in range [range_min, range_max)
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use croaring::Bitmap;
131 ///
132 /// let mut bitmap = Bitmap::create();
133 /// bitmap.add_range((1..4));
134 /// assert!(!bitmap.is_empty());
135 ///
136 /// bitmap.remove_range((1..3));
137 ///
138 /// assert!(!bitmap.contains(1));
139 /// assert!(!bitmap.contains(2));
140 /// assert!(bitmap.contains(3));
141 /// ```
142 #[inline]
143 pub fn remove_range(&mut self, range: Range<u64>) {
144 unsafe { ffi::roaring_bitmap_remove_range(self.bitmap, range.start, range.end) }
145 }
146
147 /// Add all values in range [range_min, range_max]
148 ///
149 /// # Examples
150 ///
151 /// ```
152 /// use croaring::Bitmap;
153 ///
154 /// let mut bitmap1 = Bitmap::create();
155 /// bitmap1.add_range_closed((1..3));
156 ///
157 /// assert!(!bitmap1.is_empty());
158 /// assert!(bitmap1.contains(1));
159 /// assert!(bitmap1.contains(2));
160 /// assert!(bitmap1.contains(3));
161 ///
162 /// let mut bitmap2 = Bitmap::create();
163 /// bitmap2.add_range_closed((3..1));
164 /// assert!(bitmap2.is_empty());
165 ///
166 /// let mut bitmap3 = Bitmap::create();
167 /// bitmap3.add_range_closed((3..3));
168 /// assert!(!bitmap3.is_empty());
169 /// assert!(bitmap3.contains(3));
170 /// ```
171 #[inline]
172 pub fn add_range_closed(&mut self, range: Range<u32>) {
173 unsafe { ffi::roaring_bitmap_add_range_closed(self.bitmap, range.start, range.end + 1) }
174 }
175
176 /// Remove all values in range [range_min, range_max]
177 ///
178 /// # Examples
179 ///
180 /// ```
181 /// use croaring::Bitmap;
182 ///
183 /// let mut bitmap = Bitmap::create();
184 /// bitmap.add_range((1..4));
185 /// assert!(!bitmap.is_empty());
186 ///
187 /// bitmap.remove_range_closed((1..3));
188 ///
189 /// assert!(!bitmap.contains(1));
190 /// assert!(!bitmap.contains(2));
191 /// assert!(!bitmap.contains(3));
192 /// ```
193 #[inline]
194 pub fn remove_range_closed(&mut self, range: Range<u32>) {
195 unsafe { ffi::roaring_bitmap_remove_range_closed(self.bitmap, range.start, range.end) }
196 }
197
198 /// Check whether a range of values of range are present
199 ///
200 /// # Examples
201 ///
202 /// ```
203 /// use croaring::Bitmap;
204 ///
205 /// let mut bitmap = Bitmap::create();
206 /// bitmap.add_range((1..3));
207 /// assert!(bitmap.contains_range((1..3)));
208 /// ```
209 #[inline]
210 pub fn contains_range(&mut self, range: Range<u64>) -> bool {
211 unsafe { ffi::roaring_bitmap_contains_range(self.bitmap, range.start, range.end) }
212 }
213
214 /// Empties the bitmap
215 ///
216 /// # Examples
217 ///
218 /// ```
219 /// use croaring::Bitmap;
220 ///
221 /// let mut bitmap = Bitmap::create();
222 /// bitmap.add(1);
223 /// bitmap.add(2);
224 /// bitmap.clear();
225 ///
226 /// assert!(bitmap.is_empty());
227 /// ```
228 #[inline]
229 pub fn clear(&mut self) {
230 unsafe { ffi::roaring_bitmap_clear(self.bitmap) }
231 }
232
233 /// Clear the integer element from the bitmap
234 ///
235 /// # Examples
236 ///
237 /// ```
238 /// use croaring::Bitmap;
239 ///
240 /// let mut bitmap = Bitmap::create();
241 /// bitmap.add(1);
242 /// bitmap.remove(1);
243 ///
244 /// assert!(bitmap.is_empty());
245 /// ```
246 #[inline]
247 pub fn remove(&mut self, element: u32) {
248 unsafe { ffi::roaring_bitmap_remove(self.bitmap, element) }
249 }
250
251 /// Remove the integer element from the bitmap. Returns true if a the value
252 /// was removed, false if the value was present in the bitmap.
253 ///
254 /// # Examples
255 ///
256 /// ```
257 /// use croaring::Bitmap;
258 ///
259 /// let mut bitmap = Bitmap::create();
260 /// bitmap.add(1);
261 /// assert!(bitmap.remove_checked(1));
262 /// assert!(!bitmap.remove_checked(1));
263 /// ```
264 #[inline]
265 pub fn remove_checked(&mut self, element: u32) -> bool {
266 unsafe { ffi::roaring_bitmap_remove_checked(self.bitmap, element) }
267 }
268
269 /// Contains returns true if the integer element is contained in the bitmap
270 ///
271 /// # Examples
272 ///
273 /// ```
274 /// use croaring::Bitmap;
275 ///
276 /// let mut bitmap = Bitmap::create();
277 /// bitmap.add(1);
278 ///
279 /// assert!(bitmap.contains(1));
280 /// assert!(!bitmap.contains(2));
281 /// ```
282 #[inline]
283 pub fn contains(&self, element: u32) -> bool {
284 unsafe { ffi::roaring_bitmap_contains(self.bitmap, element) }
285 }
286
287 /// Returns number of elements in range [range_start, range_end).
288 ///
289 /// # Examples
290 ///
291 /// ```
292 /// use croaring::Bitmap;
293 ///
294 /// let mut bitmap = Bitmap::create();
295 /// bitmap.add(1);
296 /// bitmap.add(3);
297 /// bitmap.add(4);
298 ///
299 /// assert_eq!(bitmap.range_cardinality((0..1)), 0);
300 /// assert_eq!(bitmap.range_cardinality((0..2)), 1);
301 /// assert_eq!(bitmap.range_cardinality((2..5)), 2);
302 /// assert_eq!(bitmap.range_cardinality((0..5)), 3);
303 /// ```
304 #[inline]
305 pub fn range_cardinality(&self, range: Range<u64>) -> u64 {
306 unsafe { ffi::roaring_bitmap_range_cardinality(self.bitmap, range.start, range.end) }
307 }
308
309 /// Returns the number of integers contained in the bitmap
310 ///
311 /// # Examples
312 ///
313 /// ```
314 /// use croaring::Bitmap;
315 ///
316 /// let mut bitmap = Bitmap::create();
317 /// bitmap.add(1);
318 ///
319 /// assert_eq!(bitmap.cardinality(), 1);
320 ///
321 /// bitmap.add(2);
322 ///
323 /// assert_eq!(bitmap.cardinality(), 2);
324 /// ```
325 #[inline]
326 pub fn cardinality(&self) -> u64 {
327 unsafe { ffi::roaring_bitmap_get_cardinality(self.bitmap) }
328 }
329
330 /// And computes the intersection between two bitmaps and returns the result
331 /// as a new bitmap
332 ///
333 /// # Examples
334 ///
335 /// ```
336 /// use croaring::Bitmap;
337 ///
338 /// let mut bitmap1 = Bitmap::create();
339 /// bitmap1.add(1);
340 ///
341 /// let mut bitmap2 = Bitmap::create();
342 /// bitmap2.add(1);
343 /// bitmap2.add(2);
344 ///
345 /// let bitmap3 = bitmap1.and(&bitmap2);
346 ///
347 /// assert!(bitmap3.contains(1));
348 /// assert!(!bitmap3.contains(2));
349 /// ```
350 #[inline]
351 pub fn and(&self, other: &Self) -> Self {
352 Bitmap {
353 bitmap: unsafe { ffi::roaring_bitmap_and(self.bitmap, other.bitmap) },
354 }
355 }
356
357 /// Computes the intersection between two bitmaps and stores the result
358 /// in the current bitmap
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// use croaring::Bitmap;
364 ///
365 /// let mut bitmap1 = Bitmap::create();
366 /// bitmap1.add(15);
367 ///
368 /// let mut bitmap2 = Bitmap::create();
369 /// bitmap2.add(25);
370 ///
371 /// let mut bitmap3 = Bitmap::create();
372 /// bitmap3.add(15);
373 ///
374 /// let mut bitmap4 = Bitmap::create();
375 /// bitmap4.add(15);
376 /// bitmap4.add(25);
377 ///
378 /// bitmap1.and_inplace(&bitmap2);
379 ///
380 /// assert!(bitmap1.cardinality() == 0);
381 /// assert!(!bitmap1.contains(15));
382 /// assert!(!bitmap1.contains(25));
383 ///
384 /// bitmap3.and_inplace(&bitmap4);
385 ///
386 /// assert!(bitmap3.cardinality() == 1);
387 /// assert!(bitmap3.contains(15));
388 /// assert!(!bitmap3.contains(25));
389 /// ```
390 #[inline]
391 pub fn and_inplace(&mut self, other: &Self) {
392 unsafe { ffi::roaring_bitmap_and_inplace(self.bitmap, other.bitmap) }
393 }
394
395 /// Or computes the union between two bitmaps and returns the result
396 /// as a new bitmap
397 ///
398 /// # Examples
399 ///
400 /// ```
401 /// use croaring::Bitmap;
402 ///
403 /// let mut bitmap1 = Bitmap::create();
404 /// bitmap1.add(15);
405 ///
406 /// let mut bitmap2 = Bitmap::create();
407 /// bitmap2.add(25);
408 ///
409 /// let bitmap3 = bitmap1.or(&bitmap2);
410 ///
411 /// assert!(bitmap3.cardinality() == 2);
412 /// assert!(bitmap3.contains(15));
413 /// assert!(bitmap3.contains(25));
414 /// ```
415 #[inline]
416 pub fn or(&self, other: &Self) -> Self {
417 Bitmap {
418 bitmap: unsafe { ffi::roaring_bitmap_or(self.bitmap, other.bitmap) },
419 }
420 }
421
422 /// Computes the union between two bitmaps and stores the result in
423 /// the current bitmap.
424 ///
425 /// # Examples
426 ///
427 /// ```
428 /// use croaring::Bitmap;
429 ///
430 /// let mut bitmap1 = Bitmap::create();
431 /// bitmap1.add(15);
432 ///
433 /// let mut bitmap2 = Bitmap::create();
434 /// bitmap2.add(25);
435 ///
436 /// bitmap1.or_inplace(&bitmap2);
437 ///
438 /// assert!(bitmap1.cardinality() == 2);
439 /// assert!(bitmap1.contains(15));
440 /// assert!(bitmap1.contains(25));
441 /// ```
442 #[inline]
443 pub fn or_inplace(&mut self, other: &Self) {
444 unsafe { ffi::roaring_bitmap_or_inplace(self.bitmap, other.bitmap) }
445 }
446
447 /// Computes the union between many bitmaps quickly, as opposed to having
448 /// to call or() repeatedly. Returns the result as a new bitmap.
449 ///
450 /// # Examples
451 ///
452 /// ```
453 /// use croaring::Bitmap;
454 ///
455 /// let mut bitmap1 = Bitmap::create();
456 /// bitmap1.add(15);
457 ///
458 /// let mut bitmap2 = Bitmap::create();
459 /// bitmap2.add(25);
460 ///
461 /// let mut bitmap3 = Bitmap::create();
462 /// bitmap3.add(35);
463 ///
464 /// let bitmap4 = Bitmap::fast_or(&[&bitmap1, &bitmap2, &bitmap3]);
465 ///
466 /// assert_eq!(bitmap4.cardinality(), 3);
467 /// assert!(bitmap4.contains(15));
468 /// assert!(bitmap4.contains(25));
469 /// assert!(bitmap4.contains(25));
470 /// ```
471 #[inline]
472 pub fn fast_or(bitmaps: &[&Bitmap]) -> Self {
473 let mut bms: Vec<*const ffi::roaring_bitmap_s> = Vec::with_capacity(bitmaps.len());
474
475 for (i, item) in bitmaps.iter().enumerate() {
476 bms.insert(i, item.bitmap);
477 }
478
479 Bitmap {
480 bitmap: unsafe { ffi::roaring_bitmap_or_many(bms.len(), bms.as_mut_ptr()) },
481 }
482 }
483
484 /// Compute the union of 'number' bitmaps using a heap. This can
485 /// sometimes be faster than Bitmap::fast_or.
486 ///
487 /// # Examples
488 ///
489 /// ```
490 /// use croaring::Bitmap;
491 ///
492 /// let mut bitmap1 = Bitmap::create();
493 /// bitmap1.add(15);
494 ///
495 /// let mut bitmap2 = Bitmap::create();
496 /// bitmap2.add(25);
497 ///
498 /// let mut bitmap3 = Bitmap::create();
499 /// bitmap3.add(35);
500 ///
501 /// let bitmap4 = Bitmap::fast_or_heap(&[&bitmap1, &bitmap2, &bitmap3]);
502 ///
503 /// assert_eq!(bitmap4.cardinality(), 3);
504 /// assert!(bitmap4.contains(15));
505 /// assert!(bitmap4.contains(25));
506 /// assert!(bitmap4.contains(25));
507 /// ```
508 #[inline]
509 pub fn fast_or_heap(bitmaps: &[&Bitmap]) -> Self {
510 let mut bms: Vec<*const ffi::roaring_bitmap_s> = Vec::with_capacity(bitmaps.len());
511
512 for (i, item) in bitmaps.iter().enumerate() {
513 bms.insert(i, item.bitmap);
514 }
515
516 Bitmap {
517 bitmap: unsafe { ffi::roaring_bitmap_or_many_heap(bms.len() as u32, bms.as_mut_ptr()) },
518 }
519 }
520
521 /// Computes the symmetric difference (xor) between two bitmaps
522 /// and returns new bitmap.
523 ///
524 /// # Examples
525 ///
526 /// ```
527 /// use croaring::Bitmap;
528 ///
529 /// let mut bitmap1 = Bitmap::create();
530 /// bitmap1.add(15);
531 /// bitmap1.add(25);
532 ///
533 /// let mut bitmap2 = Bitmap::create();
534 /// bitmap2.add(25);
535 /// bitmap2.add(35);
536 ///
537 /// let bitmap3 = bitmap1.xor(&bitmap2);
538 ///
539 /// assert!(bitmap3.cardinality() == 2);
540 /// assert!(bitmap3.contains(15));
541 /// assert!(!bitmap3.contains(25));
542 /// assert!(bitmap3.contains(35));
543 /// ```
544 #[inline]
545 pub fn xor(&self, other: &Self) -> Self {
546 Bitmap {
547 bitmap: unsafe { ffi::roaring_bitmap_xor(self.bitmap, other.bitmap) },
548 }
549 }
550
551 /// Inplace version of roaring_bitmap_xor, stores result in current bitmap.
552 ///
553 /// # Examples
554 ///
555 /// ```
556 /// use croaring::Bitmap;
557 ///
558 /// let mut bitmap1 = Bitmap::create();
559 /// bitmap1.add(15);
560 /// bitmap1.add(25);
561 ///
562 /// let mut bitmap2 = Bitmap::create();
563 /// bitmap2.add(25);
564 /// bitmap2.add(35);
565 ///
566 /// bitmap1.xor_inplace(&bitmap2);
567 ///
568 /// assert!(bitmap1.cardinality() == 2);
569 /// assert!(bitmap1.contains(15));
570 /// assert!(!bitmap1.contains(25));
571 /// assert!(bitmap1.contains(35));
572 /// ```
573 #[inline]
574 pub fn xor_inplace(&mut self, other: &Self) {
575 unsafe { ffi::roaring_bitmap_xor_inplace(self.bitmap, other.bitmap) }
576 }
577
578 /// Computes the symmetric difference (xor) between multiple bitmaps
579 /// and returns new bitmap as a result.
580 ///
581 /// # Examples
582 ///
583 /// ```
584 /// use croaring::Bitmap;
585 ///
586 /// let mut bitmap1 = Bitmap::create();
587 /// bitmap1.add(15);
588 /// bitmap1.add(25);
589 ///
590 /// let mut bitmap2 = Bitmap::create();
591 /// bitmap2.add(25);
592 /// bitmap2.add(35);
593 ///
594 /// let bitmap3 = Bitmap::fast_xor(&[&bitmap1, &bitmap2]);
595 ///
596 /// assert!(bitmap3.cardinality() == 2);
597 /// assert!(bitmap3.contains(15));
598 /// assert!(!bitmap3.contains(25));
599 /// assert!(bitmap3.contains(35));
600 /// ```
601 #[inline]
602 pub fn fast_xor(bitmaps: &[&Bitmap]) -> Self {
603 let mut bms: Vec<*const ffi::roaring_bitmap_s> = Vec::with_capacity(bitmaps.len());
604
605 for (i, item) in bitmaps.iter().enumerate() {
606 bms.insert(i, item.bitmap);
607 }
608
609 Bitmap {
610 bitmap: unsafe { ffi::roaring_bitmap_xor_many(bms.len(), bms.as_mut_ptr()) },
611 }
612 }
613
614 /// Computes the difference between two bitmaps and returns the result.
615 ///
616 /// # Examples
617 ///
618 /// ```
619 /// use croaring::Bitmap;
620 ///
621 /// let mut bitmap1 = Bitmap::create();
622 ///
623 /// bitmap1.add(15);
624 /// bitmap1.add(25);
625 ///
626 /// let mut bitmap2 = Bitmap::create();
627 ///
628 /// bitmap2.add(25);
629 /// bitmap2.add(35);
630 ///
631 /// let bitmap3 = bitmap1.andnot(&bitmap2);
632 ///
633 /// assert_eq!(bitmap3.cardinality(), 1);
634 /// assert!(bitmap3.contains(15));
635 /// assert!(!bitmap3.contains(25));
636 /// assert!(!bitmap3.contains(35));
637 /// ```
638 #[inline]
639 pub fn andnot(&self, other: &Self) -> Self {
640 Bitmap {
641 bitmap: unsafe { ffi::roaring_bitmap_andnot(self.bitmap, other.bitmap) },
642 }
643 }
644
645 /// Computes the difference between two bitmaps and stores the result
646 /// in the current bitmap.
647 ///
648 /// # Examples
649 ///
650 /// ```
651 /// use croaring::Bitmap;
652 ///
653 /// let mut bitmap1 = Bitmap::create();
654 ///
655 /// bitmap1.add(15);
656 /// bitmap1.add(25);
657 ///
658 /// let mut bitmap2 = Bitmap::create();
659 ///
660 /// bitmap2.add(25);
661 /// bitmap2.add(35);
662 ///
663 /// bitmap1.andnot_inplace(&bitmap2);
664 ///
665 /// assert_eq!(bitmap1.cardinality(), 1);
666 /// assert!(bitmap1.contains(15));
667 /// assert!(!bitmap1.contains(25));
668 /// assert!(!bitmap1.contains(35));
669 ///
670 /// let mut bitmap3 = Bitmap::create();
671 /// bitmap3.add(15);
672 /// let mut bitmap4 = Bitmap::create();
673 /// bitmap3.andnot_inplace(&bitmap4);
674 /// assert_eq!(bitmap3.cardinality(), 1);
675 /// assert!(bitmap3.contains(15));
676 /// ```
677 #[inline]
678 pub fn andnot_inplace(&mut self, other: &Self) {
679 unsafe { ffi::roaring_bitmap_andnot_inplace(self.bitmap, other.bitmap) }
680 }
681
682 /// Negates the bits in the given range (i.e., [rangeStart..rangeEnd)),
683 /// any integer present in this range and in the bitmap is removed.
684 /// Returns result as a new bitmap.
685 ///
686 /// # Examples
687 ///
688 /// ```
689 /// use croaring::Bitmap;
690 ///
691 /// let mut bitmap1 = Bitmap::create();
692 /// bitmap1.add(4);
693 ///
694 /// let bitmap2 = bitmap1.flip((1..3));
695 ///
696 /// assert_eq!(bitmap2.cardinality(), 3);
697 /// assert!(bitmap2.contains(1));
698 /// assert!(bitmap2.contains(2));
699 /// assert!(!bitmap2.contains(3));
700 /// assert!(bitmap2.contains(4));
701 /// ```
702 #[inline]
703 pub fn flip(&self, range: Range<u64>) -> Self {
704 Bitmap {
705 bitmap: unsafe { ffi::roaring_bitmap_flip(self.bitmap, range.start, range.end) },
706 }
707 }
708
709 /// Negates the bits in the given range (i.e., [rangeStart..rangeEnd)),
710 /// any integer present in this range and in the bitmap is removed.
711 /// Stores the result in the current bitmap.
712 ///
713 /// # Examples
714 ///
715 /// ```
716 /// use croaring::Bitmap;
717 ///
718 /// let mut bitmap1 = Bitmap::create();
719 /// bitmap1.add(4);
720 /// bitmap1.flip_inplace((1..3));
721 ///
722 /// assert_eq!(bitmap1.cardinality(), 3);
723 /// assert!(bitmap1.contains(1));
724 /// assert!(bitmap1.contains(2));
725 /// assert!(!bitmap1.contains(3));
726 /// assert!(bitmap1.contains(4));
727 /// ```
728 #[inline]
729 pub fn flip_inplace(&mut self, range: Range<u64>) {
730 unsafe { ffi::roaring_bitmap_flip_inplace(self.bitmap, range.start, range.end) }
731 }
732
733 /// Returns a vector containing all of the integers stored in the Bitmap
734 /// in sorted order.
735 ///
736 /// ```
737 /// use croaring::Bitmap;
738 ///
739 /// let mut bitmap = Bitmap::create();
740 /// bitmap.add(15);
741 /// bitmap.add(25);
742 ///
743 /// assert_eq!(bitmap.to_vec(), [15, 25]);
744 /// assert!(bitmap.to_vec() != [10, 15, 25]);
745 /// ```
746 #[inline]
747 pub fn to_vec(&self) -> Vec<u32> {
748 let bitmap_size = self.cardinality();
749
750 let mut buffer: Vec<u32> = Vec::with_capacity(bitmap_size as usize);
751 let buffer_ptr = buffer.as_mut_ptr();
752
753 unsafe {
754 ::std::mem::forget(buffer);
755
756 ffi::roaring_bitmap_to_uint32_array(self.bitmap, buffer_ptr);
757
758 Vec::from_raw_parts(buffer_ptr, bitmap_size as usize, bitmap_size as usize)
759 }
760 }
761
762 /// Computes the serialized size in bytes of the Bitmap.
763 #[inline]
764 pub fn get_serialized_size_in_bytes(&self) -> usize {
765 unsafe { ffi::roaring_bitmap_portable_size_in_bytes(self.bitmap) }
766 }
767
768 /// Serializes a bitmap to a slice of bytes.
769 ///
770 /// # Examples
771 ///
772 /// ```
773 /// use croaring::Bitmap;
774 ///
775 /// let original_bitmap: Bitmap = (1..5).collect();
776 ///
777 /// let serialized_buffer = original_bitmap.serialize();
778 ///
779 /// let deserialized_bitmap = Bitmap::deserialize(&serialized_buffer);
780 ///
781 /// assert_eq!(original_bitmap, deserialized_bitmap);
782 /// ```
783 #[inline]
784 pub fn serialize(&self) -> Vec<u8> {
785 let capacity = self.get_serialized_size_in_bytes();
786 let mut dst = Vec::with_capacity(capacity);
787
788 unsafe {
789 ffi::roaring_bitmap_portable_serialize(
790 self.bitmap,
791 dst.as_mut_ptr() as *mut ::libc::c_char,
792 );
793 dst.set_len(capacity);
794 }
795
796 dst
797 }
798
799 /// Given a serialized bitmap as slice of bytes returns a bitmap instance.
800 /// See example of #serialize function.
801 ///
802 /// On invalid input returns None.
803 ///
804 /// # Examples
805 ///
806 /// ```
807 /// use croaring::Bitmap;
808 ///
809 /// let original_bitmap: Bitmap = (1..5).collect();
810 /// let serialized_buffer = original_bitmap.serialize();
811 ///
812 /// let deserialized_bitmap = Bitmap::try_deserialize(&serialized_buffer);
813 /// assert_eq!(original_bitmap, deserialized_bitmap.unwrap());
814 ///
815 /// let invalid_buffer: Vec<u8> = vec![3];
816 /// let deserialized_bitmap = Bitmap::try_deserialize(&invalid_buffer);
817 /// assert!(deserialized_bitmap.is_none());
818 /// ```
819 #[inline]
820 pub fn try_deserialize(buffer: &[u8]) -> Option<Self> {
821 unsafe {
822 let bitmap = ffi::roaring_bitmap_portable_deserialize_safe(
823 buffer.as_ptr() as *const ::libc::c_char,
824 buffer.len() as ::libc::size_t
825 );
826
827 if !bitmap.is_null() {
828 Some(Bitmap { bitmap })
829 } else {
830 None
831 }
832 }
833 }
834
835 /// Given a serialized bitmap as slice of bytes returns a bitmap instance.
836 /// See example of #serialize function.
837 ///
838 /// On invalid input returns empty bitmap.
839 #[inline]
840 pub fn deserialize(buffer: &[u8]) -> Self {
841 Self::try_deserialize(buffer).unwrap_or_else(Bitmap::create)
842 }
843
844 /// Creates a new bitmap from a slice of u32 integers
845 ///
846 /// # Examples
847 ///
848 /// ```
849 /// use croaring::Bitmap;
850 ///
851 /// let elements = vec![1, 2];
852 ///
853 /// let bitmap = Bitmap::of(&elements);
854 ///
855 /// let mut bitmap2 = Bitmap::create();
856 ///
857 /// for element in &elements {
858 /// bitmap2.add(*element);
859 /// }
860 ///
861 /// assert!(bitmap.contains(1));
862 /// assert!(bitmap.contains(2));
863 /// assert!(!bitmap.contains(3));
864 /// assert_eq!(bitmap, bitmap2);
865 /// ```
866 #[inline]
867 pub fn of(elements: &[u32]) -> Self {
868 Bitmap {
869 bitmap: unsafe { ffi::roaring_bitmap_of_ptr(elements.len(), elements.as_ptr()) },
870 }
871 }
872
873 /// Compresses of the bitmap. Returns true if the bitmap was modified.
874 ///
875 /// # Examples
876 ///
877 /// ```
878 /// use croaring::Bitmap;
879 ///
880 /// let mut bitmap: Bitmap = (100..1000).collect();
881 ///
882 /// assert_eq!(bitmap.cardinality(), 900);
883 /// assert!(bitmap.run_optimize());
884 /// ```
885 #[inline]
886 pub fn run_optimize(&mut self) -> bool {
887 unsafe { ffi::roaring_bitmap_run_optimize(self.bitmap) }
888 }
889
890 /// Removes run-length encoding even when it is more space efficient. Returns
891 /// true if a change was applied.
892 ///
893 /// # Examples
894 ///
895 /// ```
896 /// use croaring::Bitmap;
897 ///
898 /// let mut bitmap: Bitmap = (100..1000).collect();
899 ///
900 /// assert_eq!(bitmap.cardinality(), 900);
901 ///
902 /// bitmap.run_optimize();
903 ///
904 /// assert!(bitmap.remove_run_compression());
905 /// assert!(!bitmap.remove_run_compression());
906 /// ```
907 #[inline]
908 pub fn remove_run_compression(&mut self) -> bool {
909 unsafe { ffi::roaring_bitmap_remove_run_compression(self.bitmap) }
910 }
911
912 /// Returns true if the Bitmap is empty.
913 /// Faster than doing: bitmap.cardinality() == 0)
914 ///
915 /// # Examples
916 ///
917 /// ```
918 /// use croaring::Bitmap;
919 ///
920 /// let mut bitmap = Bitmap::create();
921 ///
922 /// assert!(bitmap.is_empty());
923 ///
924 /// bitmap.add(1);
925 ///
926 /// assert!(!bitmap.is_empty());
927 /// ```
928 #[inline]
929 pub fn is_empty(&self) -> bool {
930 unsafe { ffi::roaring_bitmap_is_empty(self.bitmap) }
931 }
932
933 /// Return true if all the elements of Self are in &other.
934 ///
935 /// # Examples
936 ///
937 /// ```
938 /// use croaring::Bitmap;
939 ///
940 /// let bitmap1: Bitmap = (5..10).collect();
941 /// let bitmap2: Bitmap = (5..8).collect();
942 /// let bitmap3: Bitmap = (5..10).collect();
943 /// let bitmap4: Bitmap = (9..11).collect();
944 ///
945 /// assert!(bitmap2.is_subset(&bitmap1));
946 /// assert!(bitmap3.is_subset(&bitmap1));
947 /// assert!(!bitmap4.is_subset(&bitmap1));
948 /// ```
949 #[inline]
950 pub fn is_subset(&self, other: &Self) -> bool {
951 unsafe { ffi::roaring_bitmap_is_subset(self.bitmap, other.bitmap) }
952 }
953
954 /// Return true if all the elements of Self are in &other and &other is strictly greater
955 /// than Self.
956 ///
957 /// # Examples
958 ///
959 /// ```
960 /// use croaring::Bitmap;
961 ///
962 /// let bitmap1: Bitmap = (5..9).collect();
963 /// let bitmap2: Bitmap = (5..8).collect();
964 /// let bitmap3: Bitmap = (5..10).collect();
965 /// let bitmap4: Bitmap = (9..11).collect();
966 ///
967 /// assert!(bitmap2.is_subset(&bitmap1));
968 /// assert!(!bitmap3.is_subset(&bitmap1));
969 /// assert!(!bitmap4.is_subset(&bitmap1));
970 /// ```
971 #[inline]
972 pub fn is_strict_subset(&self, other: &Self) -> bool {
973 unsafe { ffi::roaring_bitmap_is_strict_subset(self.bitmap, other.bitmap) }
974 }
975
976 /// Return true if Self and &other intersect
977 ///
978 /// # Examples
979 ///
980 /// ```
981 /// use croaring::Bitmap;
982 ///
983 /// let bitmap1: Bitmap = (1..5).collect();
984 /// let bitmap2: Bitmap = (5..9).collect();
985 /// let bitmap3: Bitmap = (3..7).collect();
986 ///
987 /// assert_eq!(bitmap1.intersect(&bitmap2), false);
988 /// assert_eq!(bitmap1.intersect(&bitmap3), true);
989 /// assert_eq!(bitmap2.intersect(&bitmap3), true);
990 /// ```
991 #[inline]
992 pub fn intersect(&self, other: &Self) -> bool {
993 unsafe { ffi::roaring_bitmap_intersect(self.bitmap, other.bitmap) }
994 }
995
996 /// Return the Jaccard index between Self and &other
997 ///
998 /// ```
999 /// use croaring::Bitmap;
1000 ///
1001 /// let bitmap1: Bitmap = (1..5).collect();
1002 /// let bitmap2: Bitmap = (5..9).collect();
1003 /// let bitmap3: Bitmap = (3..9).collect();
1004 ///
1005 /// assert_eq!(bitmap1.jaccard_index(&bitmap2), 0.0);
1006 /// assert_eq!(bitmap1.jaccard_index(&bitmap3), 0.25);
1007 /// assert_eq!(bitmap2.jaccard_index(&bitmap3), 0.6666666666666666);
1008 /// ```
1009 #[inline]
1010 pub fn jaccard_index(&self, other: &Self) -> f64 {
1011 unsafe { ffi::roaring_bitmap_jaccard_index(self.bitmap, other.bitmap) }
1012 }
1013
1014 /// Return the size of the intersection between Self and &other
1015 ///
1016 /// # Examples
1017 ///
1018 /// ```
1019 /// use croaring::Bitmap;
1020 ///
1021 /// let mut bitmap1 = Bitmap::create();
1022 /// bitmap1.add(1);
1023 ///
1024 /// let mut bitmap2 = Bitmap::create();
1025 /// bitmap2.add(1);
1026 /// bitmap2.add(2);
1027 ///
1028 /// assert_eq!(bitmap1.and_cardinality(&bitmap2), 1);
1029 /// ```
1030 #[inline]
1031 pub fn and_cardinality(&self, other: &Self) -> u64 {
1032 unsafe { ffi::roaring_bitmap_and_cardinality(self.bitmap, other.bitmap) }
1033 }
1034
1035 /// Return the size of the union between Self and &other
1036 ///
1037 /// # Examples
1038 ///
1039 /// ```
1040 /// use croaring::Bitmap;
1041 ///
1042 /// let mut bitmap1 = Bitmap::create();
1043 /// bitmap1.add(15);
1044 ///
1045 /// let mut bitmap2 = Bitmap::create();
1046 /// bitmap2.add(25);
1047 ///
1048 /// assert_eq!(bitmap1.or_cardinality(&bitmap2), 2);
1049 #[inline]
1050 pub fn or_cardinality(&self, other: &Self) -> u64 {
1051 unsafe { ffi::roaring_bitmap_or_cardinality(self.bitmap, other.bitmap) }
1052 }
1053
1054 /// Return the size of the difference between Self and &other
1055 ///
1056 /// # Examples
1057 ///
1058 /// ```
1059 /// use croaring::Bitmap;
1060 ///
1061 /// let mut bitmap1 = Bitmap::create();
1062 ///
1063 /// bitmap1.add(15);
1064 /// bitmap1.add(25);
1065 ///
1066 /// let mut bitmap2 = Bitmap::create();
1067 ///
1068 /// bitmap2.add(25);
1069 /// bitmap2.add(35);
1070 ///
1071 /// assert_eq!(bitmap1.andnot_cardinality(&bitmap2), 1);
1072 /// ```
1073 #[inline]
1074 pub fn andnot_cardinality(&self, other: &Self) -> u64 {
1075 unsafe { ffi::roaring_bitmap_andnot_cardinality(self.bitmap, other.bitmap) }
1076 }
1077
1078 /// Return the size of the symmetric difference between Self and &other
1079 ///
1080 /// # Examples
1081 ///
1082 /// ```
1083 /// use croaring::Bitmap;
1084 ///
1085 /// let mut bitmap1 = Bitmap::create();
1086 /// bitmap1.add(15);
1087 /// bitmap1.add(25);
1088 ///
1089 /// let mut bitmap2 = Bitmap::create();
1090 /// bitmap2.add(25);
1091 /// bitmap2.add(35);
1092 ///
1093 /// assert_eq!(bitmap1.xor_cardinality(&bitmap2), 2);
1094 /// ```
1095 #[inline]
1096 pub fn xor_cardinality(&self, other: &Self) -> u64 {
1097 unsafe { ffi::roaring_bitmap_xor_cardinality(self.bitmap, other.bitmap) }
1098 }
1099
1100 /// Returns the smallest value in the set.
1101 /// Returns std::u32::MAX if the set is empty.
1102 ///
1103 /// # Examples
1104 ///
1105 /// ```
1106 /// use croaring::Bitmap;
1107 ///
1108 /// let mut bitmap: Bitmap = (5..10).collect();
1109 /// let empty_bitmap: Bitmap = Bitmap::create();
1110 ///
1111 /// assert_eq!(bitmap.minimum(), Some(5));
1112 /// assert_eq!(empty_bitmap.minimum(), None);
1113 ///
1114 /// bitmap.add(3);
1115 ///
1116 /// assert_eq!(bitmap.minimum(), Some(3));
1117 /// ```
1118 #[inline]
1119 pub fn minimum(&self) -> Option<u32> {
1120 if self.is_empty() {
1121 None
1122 } else {
1123 Some(unsafe { ffi::roaring_bitmap_minimum(self.bitmap) })
1124 }
1125 }
1126
1127 /// Returns the greatest value in the set.
1128 /// Returns 0 if the set is empty.
1129 ///
1130 /// # Examples
1131 ///
1132 /// ```
1133 /// use croaring::Bitmap;
1134 ///
1135 /// let mut bitmap: Bitmap = (5..10).collect();
1136 /// let empty_bitmap: Bitmap = Bitmap::create();
1137 ///
1138 /// assert_eq!(bitmap.maximum(), Some(9));
1139 /// assert_eq!(empty_bitmap.maximum(), None);
1140 ///
1141 /// bitmap.add(15);
1142 ///
1143 /// assert_eq!(bitmap.maximum(), Some(15));
1144 /// ```
1145 #[inline]
1146 pub fn maximum(&self) -> Option<u32> {
1147 if self.is_empty() {
1148 None
1149 } else {
1150 Some(unsafe { ffi::roaring_bitmap_maximum(self.bitmap) })
1151 }
1152 }
1153
1154 /// Rank returns the number of values smaller or equal to x.
1155 ///
1156 /// # Examples
1157 ///
1158 /// ```
1159 /// use croaring::Bitmap;
1160 ///
1161 /// let mut bitmap: Bitmap = (5..10).collect();
1162 ///
1163 /// assert_eq!(bitmap.rank(8), 4);
1164 ///
1165 /// bitmap.add(15);
1166 ///
1167 /// assert_eq!(bitmap.rank(11), 5);
1168 /// ```
1169 #[inline]
1170 pub fn rank(&self, x: u32) -> u64 {
1171 unsafe { ffi::roaring_bitmap_rank(self.bitmap, x) }
1172 }
1173
1174 /// Select returns the element having the designated rank, if it exists
1175 /// If the size of the roaring bitmap is strictly greater than rank,
1176 /// then this function returns element of given rank wrapped in Some.
1177 /// Otherwise, it returns None.
1178 ///
1179 /// # Examples
1180 ///
1181 /// ```
1182 /// use croaring::Bitmap;
1183 ///
1184 /// let bitmap: Bitmap = (5..10).collect();
1185 ///
1186 /// assert_eq!(bitmap.select(0), Some(5));
1187 /// assert_eq!(bitmap.select(1), Some(6));
1188 /// assert_eq!(bitmap.select(2), Some(7));
1189 /// assert_eq!(bitmap.select(3), Some(8));
1190 /// assert_eq!(bitmap.select(4), Some(9));
1191 /// assert_eq!(bitmap.select(5), None);
1192 /// ```
1193 #[inline]
1194 pub fn select(&self, rank: u32) -> Option<u32> {
1195 let mut element: u32 = 0;
1196 let result = unsafe { ffi::roaring_bitmap_select(self.bitmap, rank, &mut element) };
1197
1198 if result {
1199 Some(element)
1200 } else {
1201 None
1202 }
1203 }
1204
1205 /// Returns statistics about the composition of a roaring bitmap.
1206 ///
1207 /// # Examples
1208 ///
1209 /// ```
1210 /// use croaring::Bitmap;
1211 ///
1212 /// let mut bitmap: Bitmap = (1..100).collect();
1213 /// let statistics = bitmap.statistics();
1214 ///
1215 /// assert_eq!(statistics.n_containers, 1);
1216 /// assert_eq!(statistics.n_array_containers, 1);
1217 /// assert_eq!(statistics.n_run_containers, 0);
1218 /// assert_eq!(statistics.n_bitset_containers, 0);
1219 /// assert_eq!(statistics.n_values_array_containers, 99);
1220 /// assert_eq!(statistics.n_values_run_containers, 0);
1221 /// assert_eq!(statistics.n_values_bitset_containers, 0);
1222 /// assert_eq!(statistics.n_bytes_array_containers, 198);
1223 /// assert_eq!(statistics.n_bytes_run_containers, 0);
1224 /// assert_eq!(statistics.n_bytes_bitset_containers, 0);
1225 /// assert_eq!(statistics.max_value, 99);
1226 /// assert_eq!(statistics.min_value, 1);
1227 /// assert_eq!(statistics.sum_value, 4950);
1228 /// assert_eq!(statistics.cardinality, 99);
1229 ///
1230 /// bitmap.run_optimize();
1231 /// let statistics = bitmap.statistics();
1232 ///
1233 /// assert_eq!(statistics.n_containers, 1);
1234 /// assert_eq!(statistics.n_array_containers, 0);
1235 /// assert_eq!(statistics.n_run_containers, 1);
1236 /// assert_eq!(statistics.n_bitset_containers, 0);
1237 /// assert_eq!(statistics.n_values_array_containers, 0);
1238 /// assert_eq!(statistics.n_values_run_containers, 99);
1239 /// assert_eq!(statistics.n_values_bitset_containers, 0);
1240 /// assert_eq!(statistics.n_bytes_array_containers, 0);
1241 /// assert_eq!(statistics.n_bytes_run_containers, 6);
1242 /// assert_eq!(statistics.n_bytes_bitset_containers, 0);
1243 /// assert_eq!(statistics.max_value, 99);
1244 /// assert_eq!(statistics.min_value, 1);
1245 /// assert_eq!(statistics.sum_value, 4950);
1246 /// assert_eq!(statistics.cardinality, 99);
1247 /// ```
1248 pub fn statistics(&self) -> Statistics {
1249 let mut statistics: ffi::roaring_statistics_s = unsafe { ::std::mem::zeroed() };
1250
1251 unsafe { ffi::roaring_bitmap_statistics(self.bitmap, &mut statistics) };
1252
1253 statistics
1254 }
1255}