Struct Bitmap 

pub struct Bitmap(pub RoaringBitmap);

A compressed bitmap representing a set of journal entry indices.

Wraps RoaringBitmap and supports bitwise AND/OR operations for combining filters.

Tuple Fields

0: RoaringBitmap

Implementations

impl Bitmap

pub fn new() -> Self

Create an empty bitmap.

pub fn from_sorted_iter<I: IntoIterator<Item = u32>>( iterator: I, ) -> Result<Bitmap, NonSortedIntegers>

Create a bitmap from a sorted iterator of entry indices.

pub fn insert_range<R>(range: R) -> Self

where R: RangeBounds<u32>,

Create a bitmap containing all integers in the given range.

Methods from Deref<Target = RoaringBitmap>

pub fn statistics(&self) -> Statistics

Returns statistics about the composition of a roaring bitmap.

use roaring::RoaringBitmap;

let mut bitmap: RoaringBitmap = (1..100).collect();
let statistics = bitmap.statistics();

assert_eq!(statistics.n_containers, 1);
assert_eq!(statistics.n_array_containers, 1);
assert_eq!(statistics.n_run_containers, 0);
assert_eq!(statistics.n_bitset_containers, 0);
assert_eq!(statistics.n_values_array_containers, 99);
assert_eq!(statistics.n_values_run_containers, 0);
assert_eq!(statistics.n_values_bitset_containers, 0);
assert_eq!(statistics.n_bytes_array_containers, 512);
assert_eq!(statistics.n_bytes_run_containers, 0);
assert_eq!(statistics.n_bytes_bitset_containers, 0);
assert_eq!(statistics.max_value, Some(99));
assert_eq!(statistics.min_value, Some(1));
assert_eq!(statistics.cardinality, 99);

pub fn is_disjoint(&self, other: &RoaringBitmap) -> bool

Returns true if the set has no elements in common with other. This is equivalent to checking for an empty intersection.

Examples

use roaring::RoaringBitmap;

let mut rb1 = RoaringBitmap::new();
let mut rb2 = RoaringBitmap::new();

rb1.insert(1);

assert_eq!(rb1.is_disjoint(&rb2), true);

rb2.insert(1);

assert_eq!(rb1.is_disjoint(&rb2), false);

pub fn is_subset(&self, other: &RoaringBitmap) -> bool

Returns true if this set is a subset of other.

Examples

use roaring::RoaringBitmap;

let mut rb1 = RoaringBitmap::new();
let mut rb2 = RoaringBitmap::new();

rb1.insert(1);

assert_eq!(rb1.is_subset(&rb2), false);

rb2.insert(1);

assert_eq!(rb1.is_subset(&rb2), true);

rb1.insert(2);

assert_eq!(rb1.is_subset(&rb2), false);

pub fn is_superset(&self, other: &RoaringBitmap) -> bool

Returns true if this set is a superset of other.

Examples

use roaring::RoaringBitmap;

let mut rb1 = RoaringBitmap::new();
let mut rb2 = RoaringBitmap::new();

rb1.insert(1);

assert_eq!(rb2.is_superset(&rb1), false);

rb2.insert(1);

assert_eq!(rb2.is_superset(&rb1), true);

rb1.insert(2);

assert_eq!(rb2.is_superset(&rb1), false);

pub fn insert(&mut self, value: u32) -> bool

Adds a value to the set.

Returns whether the value was absent from the set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.insert(3), true);
assert_eq!(rb.insert(3), false);
assert_eq!(rb.contains(3), true);

pub fn insert_range<R>(&mut self, range: R) -> u64

where R: RangeBounds<u32>,

Inserts a range of values. Returns the number of inserted values.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert_range(2..4);
assert!(rb.contains(2));
assert!(rb.contains(3));
assert!(!rb.contains(4));

pub fn push(&mut self, value: u32) -> bool

👎Deprecated since 0.11.0:

use try_push instead

Pushes value in the bitmap only if it is greater than the current maximum value.

Returns whether the value was inserted.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert!(rb.push(1));
assert!(rb.push(3));
assert_eq!(rb.push(3), false);
assert!(rb.push(5));

assert_eq!(rb.iter().collect::<Vec<u32>>(), vec![1, 3, 5]);

pub fn try_push(&mut self, value: u32) -> Result<(), IntegerTooSmall>

Pushes value in the bitmap only if it is greater than the current maximum value.

Returns an error if the value is not greater than the current maximum value.

Examples

use roaring::{RoaringBitmap, IntegerTooSmall};

let mut rb = RoaringBitmap::new();
assert!(rb.try_push(1).is_ok());
assert!(rb.try_push(3).is_ok());
assert_eq!(rb.try_push(3), Err(IntegerTooSmall));
assert!(rb.try_push(5).is_ok());

assert_eq!(rb.iter().collect::<Vec<u32>>(), vec![1, 3, 5]);

pub fn remove(&mut self, value: u32) -> bool

Removes a value from the set. Returns true if the value was present in the set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert(3);
assert_eq!(rb.remove(3), true);
assert_eq!(rb.remove(3), false);
assert_eq!(rb.contains(3), false);

pub fn remove_range<R>(&mut self, range: R) -> u64

where R: RangeBounds<u32>,

Removes a range of values. Returns the number of removed values.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert(2);
rb.insert(3);
assert_eq!(rb.remove_range(2..4), 2);

pub fn contains(&self, value: u32) -> bool

Returns true if this set contains the specified integer.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert(1);
assert_eq!(rb.contains(0), false);
assert_eq!(rb.contains(1), true);
assert_eq!(rb.contains(100), false);

pub fn contains_range<R>(&self, range: R) -> bool

where R: RangeBounds<u32>,

Returns true if all values in the range are present in this set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
// An empty range is always contained
assert!(rb.contains_range(7..7));

rb.insert_range(1..0xFFF);
assert!(rb.contains_range(1..0xFFF));
assert!(rb.contains_range(2..0xFFF));
// 0 is not contained
assert!(!rb.contains_range(0..2));
// 0xFFF is not contained
assert!(!rb.contains_range(1..=0xFFF));

pub fn range_cardinality<R>(&self, range: R) -> u64

where R: RangeBounds<u32>,

Returns the number of elements in this set which are in the passed range.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert_range(0x10000..0x40000);
rb.insert(0x50001);
rb.insert(0x50005);
rb.insert(u32::MAX);

assert_eq!(rb.range_cardinality(0..0x10000), 0);
assert_eq!(rb.range_cardinality(0x10000..0x40000), 0x30000);
assert_eq!(rb.range_cardinality(0x50000..0x60000), 2);
assert_eq!(rb.range_cardinality(0x10000..0x10000), 0);
assert_eq!(rb.range_cardinality(0x50000..=u32::MAX), 3);

pub fn clear(&mut self)

Clears all integers in this set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
rb.insert(1);
assert_eq!(rb.contains(1), true);
rb.clear();
assert_eq!(rb.contains(1), false);

pub fn is_empty(&self) -> bool

Returns true if there are no integers in this set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.is_empty(), true);

rb.insert(3);
assert_eq!(rb.is_empty(), false);

pub fn is_full(&self) -> bool

Returns true if there are every possible integers in this set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::full();
assert!(!rb.is_empty());
assert!(rb.is_full());

pub fn len(&self) -> u64

Returns the number of distinct integers added to the set.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.len(), 0);

rb.insert(3);
assert_eq!(rb.len(), 1);

rb.insert(3);
rb.insert(4);
assert_eq!(rb.len(), 2);

pub fn min(&self) -> Option<u32>

Returns the minimum value in the set (if the set is non-empty).

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.min(), None);

rb.insert(3);
rb.insert(4);
assert_eq!(rb.min(), Some(3));

pub fn max(&self) -> Option<u32>

Returns the maximum value in the set (if the set is non-empty).

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.max(), None);

rb.insert(3);
rb.insert(4);
assert_eq!(rb.max(), Some(4));

pub fn rank(&self, value: u32) -> u64

Returns the number of integers that are <= value. rank(u32::MAX) == len()

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.rank(0), 0);

rb.insert(3);
rb.insert(4);
assert_eq!(rb.rank(3), 1);
assert_eq!(rb.rank(10), 2)

pub fn select(&self, n: u32) -> Option<u32>

Returns the nth integer in the set or None if n >= len()

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.select(0), None);

rb.append(vec![0, 10, 100]);

assert_eq!(rb.select(0), Some(0));
assert_eq!(rb.select(1), Some(10));
assert_eq!(rb.select(2), Some(100));
assert_eq!(rb.select(3), None);

pub fn remove_smallest(&mut self, n: u64)

Removes the n smallests values from this bitmap.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::from_iter([1, 5, 7, 9]);
rb.remove_smallest(2);
assert_eq!(rb, RoaringBitmap::from_iter([7, 9]));

let mut rb = RoaringBitmap::from_iter([1, 3, 7, 9]);
rb.remove_smallest(2);
assert_eq!(rb, RoaringBitmap::from_iter([7, 9]));

pub fn remove_biggest(&mut self, n: u64)

Removes the n biggests values from this bitmap.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::from_iter([1, 5, 7, 9]);
rb.remove_biggest(2);
assert_eq!(rb, RoaringBitmap::from_iter([1, 5]));
rb.remove_biggest(1);
assert_eq!(rb, RoaringBitmap::from_iter([1]));

pub fn optimize(&mut self) -> bool

Optimizes the container storage for this bitmap. Returns true if the container storage was modified, false if not.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::from_iter(1000..100000);
rb.optimize();

pub fn remove_run_compression(&mut self) -> bool

Removes run-length encoding even when it is more space efficient.

Returns true if the container storage was modified, false if not.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::from_iter(0..=10000);
rb.optimize();
assert!(rb.remove_run_compression());

pub fn iter(&self) -> Iter<'_>

Iterator over each value stored in the RoaringBitmap, guarantees values are ordered by value.

Examples

use roaring::RoaringBitmap;
use core::iter::FromIterator;

let bitmap = (1..3).collect::<RoaringBitmap>();
let mut iter = bitmap.iter();

assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), None);

pub fn range<R>(&self, range: R) -> Iter<'_>

where R: RangeBounds<u32>,

Iterator over values within a range stored in the RoaringBitmap.

Examples

use core::ops::Bound;
use roaring::RoaringBitmap;

let bitmap = RoaringBitmap::from([0, 1, 2, 3, 4, 5, 10, 11, 12, 20, 21, u32::MAX]);
let mut iter = bitmap.range(10..20);

assert_eq!(iter.next(), Some(10));
assert_eq!(iter.next(), Some(11));
assert_eq!(iter.next(), Some(12));
assert_eq!(iter.next(), None);

let mut iter = bitmap.range(100..);
assert_eq!(iter.next(), Some(u32::MAX));
assert_eq!(iter.next(), None);

let mut iter = bitmap.range((Bound::Excluded(0), Bound::Included(10)));
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), Some(4));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), Some(10));
assert_eq!(iter.next(), None);

pub fn append<I>(&mut self, iterator: I) -> Result<u64, NonSortedIntegers>

where I: IntoIterator<Item = u32>,

Extend the set with a sorted iterator.

The values of the iterator must be ordered and strictly greater than the greatest value in the set. If a value in the iterator doesn’t satisfy this requirement, it is not added and the append operation is stopped.

Returns Ok with the number of elements appended to the set, Err with the number of elements we effectively appended before an error occurred.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();
assert_eq!(rb.append(0..10), Ok(10));

assert!(rb.iter().eq(0..10));

pub fn intersection_len(&self, other: &RoaringBitmap) -> u64

Computes the len of the intersection with the specified other bitmap without creating a new bitmap.

This is faster and more space efficient when you’re only interested in the cardinality of the intersection.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let rb2: RoaringBitmap = (3..5).collect();


assert_eq!(rb1.intersection_len(&rb2), (rb1 & rb2).len());

pub fn union_len(&self, other: &RoaringBitmap) -> u64

Computes the len of the union with the specified other bitmap without creating a new bitmap.

This is faster and more space efficient when you’re only interested in the cardinality of the union.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let rb2: RoaringBitmap = (3..5).collect();


assert_eq!(rb1.union_len(&rb2), (rb1 | rb2).len());

pub fn difference_len(&self, other: &RoaringBitmap) -> u64

Computes the len of the difference with the specified other bitmap without creating a new bitmap.

This is faster and more space efficient when you’re only interested in the cardinality of the difference.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let rb2: RoaringBitmap = (3..5).collect();


assert_eq!(rb1.difference_len(&rb2), (rb1 - rb2).len());

pub fn symmetric_difference_len(&self, other: &RoaringBitmap) -> u64

Computes the len of the symmetric difference with the specified other bitmap without creating a new bitmap.

This is faster and more space efficient when you’re only interested in the cardinality of the symmetric difference.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let rb2: RoaringBitmap = (3..5).collect();


assert_eq!(rb1.symmetric_difference_len(&rb2), (rb1 ^ rb2).len());

pub fn intersection_with_serialized_unchecked<R>( &self, other: R, ) -> Result<RoaringBitmap, Error>

where R: Read + Seek,

Computes the intersection between a materialized RoaringBitmap and a serialized one.

This is faster and more space efficient when you only need the intersection result. It reduces the number of deserialized internal container and therefore the number of allocations and copies of bytes.

Examples

use roaring::RoaringBitmap;
use std::io::Cursor;

let rb1: RoaringBitmap = (1..4).collect();
let rb2: RoaringBitmap = (3..5).collect();

// Let's say the rb2 bitmap is serialized
let mut bytes = Vec::new();
rb2.serialize_into(&mut bytes).unwrap();
let rb2_bytes = Cursor::new(bytes);

assert_eq!(
    rb1.intersection_with_serialized_unchecked(rb2_bytes).unwrap(),
    rb1 & rb2,
);

pub fn serialized_size(&self) -> usize

Return the size in bytes of the serialized output. This is compatible with the official C/C++, Java and Go implementations.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let mut bytes = Vec::with_capacity(rb1.serialized_size());
rb1.serialize_into(&mut bytes).unwrap();
let rb2 = RoaringBitmap::deserialize_from(&bytes[..]).unwrap();

assert_eq!(rb1, rb2);

pub fn serialize_into<W>(&self, writer: W) -> Result<(), Error>

where W: Write,

Serialize this bitmap into the standard Roaring on-disk format. This is compatible with the official C/C++, Java and Go implementations.

Examples

use roaring::RoaringBitmap;

let rb1: RoaringBitmap = (1..4).collect();
let mut bytes = vec![];
rb1.serialize_into(&mut bytes).unwrap();
let rb2 = RoaringBitmap::deserialize_from(&bytes[..]).unwrap();

assert_eq!(rb1, rb2);

Trait Implementations

impl BitAnd for &Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: &Bitmap) -> Bitmap

Performs the & operation.

impl BitAnd for Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: Bitmap) -> Bitmap

Performs the & operation.

impl BitAnd<&Bitmap> for Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: &Bitmap) -> Bitmap

Performs the & operation.

impl BitAnd<Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: Bitmap) -> Bitmap

Performs the & operation.

impl BitAndAssign for Bitmap

fn bitand_assign(&mut self, rhs: Bitmap)

Performs the &= operation.

impl BitAndAssign<&Bitmap> for Bitmap

fn bitand_assign(&mut self, rhs: &Bitmap)

Performs the &= operation.

impl BitOrAssign for Bitmap

fn bitor_assign(&mut self, rhs: Bitmap)

Performs the |= operation.

impl BitOrAssign<&Bitmap> for Bitmap

fn bitor_assign(&mut self, rhs: &Bitmap)

Performs the |= operation.

impl Clone for Bitmap

fn clone(&self) -> Bitmap

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Bitmap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Bitmap

fn default() -> Bitmap

Returns the “default value” for a type.

impl Deref for Bitmap

type Target = RoaringBitmap

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl DerefMut for Bitmap

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<'de> Deserialize<'de> for Bitmap

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl From<Bitmap> for RoaringBitmap

fn from(wrapper: Bitmap) -> Self

Converts to this type from the input type.

impl From<RoaringBitmap> for Bitmap

fn from(bitmap: RoaringBitmap) -> Self

Converts to this type from the input type.

impl Serialize for Bitmap

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.