Struct roaring::bitmap::RoaringBitmap

pub struct RoaringBitmap { /* private fields */ }

A compressed bitmap using the Roaring bitmap compression scheme.

Examples

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::new();

// insert all primes less than 10
rb.insert(2);
rb.insert(3);
rb.insert(5);
rb.insert(7);
println!("total bits set to true: {}", rb.len());

Implementations

impl RoaringBitmap

pub fn is_disjoint(&self, other: &Self) -> 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: &Self) -> 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: &Self) -> 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);

impl RoaringBitmap

pub fn new() -> RoaringBitmap

Creates an empty RoaringBitmap.

Examples

use roaring::RoaringBitmap;
let rb = RoaringBitmap::new();

pub fn full() -> RoaringBitmap

Creates a full RoaringBitmap.

Examples

use roaring::RoaringBitmap;
let rb = RoaringBitmap::full();

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

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 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]));

impl RoaringBitmap

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);

impl RoaringBitmap

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

Create the set from a sorted iterator. Values must be sorted and deduplicated.

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 requested RoaringBitmap, Err with the number of elements that were correctly appended before failure.

Example: Create a set from an ordered list of integers.

use roaring::RoaringBitmap;

let mut rb = RoaringBitmap::from_sorted_iter(0..10).unwrap();

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

Example: Try to create a set from a non-ordered list of integers.

use roaring::RoaringBitmap;

let integers = 0..10u32;
let error = RoaringBitmap::from_sorted_iter(integers.rev()).unwrap_err();

assert_eq!(error.valid_until(), 1);

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

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));

impl RoaringBitmap

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());

impl RoaringBitmap

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: Write>(&self, writer: W) -> Result<()>

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);

pub fn deserialize_from<R: Read>(reader: R) -> Result<RoaringBitmap>

Deserialize a bitmap into memory from the standard Roaring on-disk format. This is compatible with the official C/C++, Java and Go implementations. This method checks that all of the internal values are valid. If deserializing from a trusted source consider RoaringBitmap::deserialize_unchecked_from

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);

pub fn deserialize_unchecked_from<R: Read>(reader: R) -> Result<RoaringBitmap>

Deserialize a bitmap into memory from the standard Roaring on-disk format. This is compatible with the official C/C++, Java and Go implementations. This method is memory safe but will not check if the data is a valid bitmap.

Examples

use roaring::RoaringBitmap;

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

assert_eq!(rb1, rb2);

Trait Implementations

impl BitAnd<&RoaringBitmap> for &RoaringBitmap

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

An intersection between two sets.

type Output = RoaringBitmap

The resulting type after applying the & operator.

impl BitAnd<&RoaringBitmap> for RoaringBitmap

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

An intersection between two sets.

type Output = RoaringBitmap

The resulting type after applying the & operator.

impl BitAnd<RoaringBitmap> for &RoaringBitmap

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

An intersection between two sets.

type Output = RoaringBitmap

The resulting type after applying the & operator.

impl BitAnd for RoaringBitmap

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

An intersection between two sets.

type Output = RoaringBitmap

The resulting type after applying the & operator.

impl BitAndAssign<&RoaringBitmap> for RoaringBitmap

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

An intersection between two sets.

impl BitAndAssign for RoaringBitmap

fn bitand_assign(&mut self, rhs: RoaringBitmap)

An intersection between two sets.

impl BitOr<&RoaringBitmap> for &RoaringBitmap

fn bitor(self, rhs: &RoaringBitmap) -> RoaringBitmap

An union between two sets.

type Output = RoaringBitmap

The resulting type after applying the | operator.

impl BitOr<&RoaringBitmap> for RoaringBitmap

fn bitor(self, rhs: &RoaringBitmap) -> RoaringBitmap

An union between two sets.

type Output = RoaringBitmap

The resulting type after applying the | operator.

impl BitOr<RoaringBitmap> for &RoaringBitmap

fn bitor(self, rhs: RoaringBitmap) -> RoaringBitmap

An union between two sets.

type Output = RoaringBitmap

The resulting type after applying the | operator.

impl BitOr for RoaringBitmap

fn bitor(self, rhs: RoaringBitmap) -> RoaringBitmap

An union between two sets.

type Output = RoaringBitmap

The resulting type after applying the | operator.

impl BitOrAssign<&RoaringBitmap> for RoaringBitmap

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

An union between two sets.

impl BitOrAssign for RoaringBitmap

fn bitor_assign(&mut self, rhs: RoaringBitmap)

An union between two sets.

impl BitXor<&RoaringBitmap> for &RoaringBitmap

fn bitxor(self, rhs: &RoaringBitmap) -> RoaringBitmap

A symmetric difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the ^ operator.

impl BitXor<&RoaringBitmap> for RoaringBitmap

fn bitxor(self, rhs: &RoaringBitmap) -> RoaringBitmap

A symmetric difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the ^ operator.

impl BitXor<RoaringBitmap> for &RoaringBitmap

fn bitxor(self, rhs: RoaringBitmap) -> RoaringBitmap

A symmetric difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the ^ operator.

impl BitXor for RoaringBitmap

fn bitxor(self, rhs: RoaringBitmap) -> RoaringBitmap

A symmetric difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the ^ operator.

impl BitXorAssign<&RoaringBitmap> for RoaringBitmap

fn bitxor_assign(&mut self, rhs: &RoaringBitmap)

A symmetric difference between two sets.

impl BitXorAssign for RoaringBitmap

fn bitxor_assign(&mut self, rhs: RoaringBitmap)

A symmetric difference between two sets.

impl Clone for RoaringBitmap

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for RoaringBitmap

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

Formats the value using the given formatter.

impl Default for RoaringBitmap

fn default() -> RoaringBitmap

Returns the “default value” for a type.

impl<'a> Extend<&'a u32> for RoaringBitmap

fn extend<I: IntoIterator<Item = &'a u32>>(&mut self, iterator: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl Extend<u32> for RoaringBitmap

fn extend<I: IntoIterator<Item = u32>>(&mut self, iterator: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<const N: usize> From<[u32; N]> for RoaringBitmap

fn from(arr: [u32; N]) -> Self

Converts to this type from the input type.

impl<'a> FromIterator<&'a u32> for RoaringBitmap

fn from_iter<I: IntoIterator<Item = &'a u32>>(iterator: I) -> RoaringBitmap

Creates a value from an iterator.

impl FromIterator<u32> for RoaringBitmap

fn from_iter<I: IntoIterator<Item = u32>>(iterator: I) -> RoaringBitmap

Creates a value from an iterator.

impl<'a> IntoIterator for &'a RoaringBitmap

type Item = u32

The type of the elements being iterated over.

type IntoIter = Iter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a>

Creates an iterator from a value.

impl IntoIterator for RoaringBitmap

type Item = u32

The type of the elements being iterated over.

type IntoIter = IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter

Creates an iterator from a value.

impl<'a, I> MultiOps<&'a RoaringBitmap> for I

where I: IntoIterator<Item = &'a RoaringBitmap>,

type Output = RoaringBitmap

The type of output from operations.

fn union(self) -> Self::Output

The union between all elements.

fn intersection(self) -> Self::Output

The intersection between all elements.

fn difference(self) -> Self::Output

The difference between all elements.

fn symmetric_difference(self) -> Self::Output

The symmetric difference between all elements.

impl<I> MultiOps<RoaringBitmap> for I

where I: IntoIterator<Item = RoaringBitmap>,

type Output = RoaringBitmap

The type of output from operations.

fn union(self) -> Self::Output

The union between all elements.

fn intersection(self) -> Self::Output

The intersection between all elements.

fn difference(self) -> Self::Output

The difference between all elements.

fn symmetric_difference(self) -> Self::Output

The symmetric difference between all elements.

impl PartialEq for RoaringBitmap

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

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Sub<&RoaringBitmap> for &RoaringBitmap

fn sub(self, rhs: &RoaringBitmap) -> RoaringBitmap

A difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the - operator.

impl Sub<&RoaringBitmap> for RoaringBitmap

fn sub(self, rhs: &RoaringBitmap) -> RoaringBitmap

A difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the - operator.

impl Sub<RoaringBitmap> for &RoaringBitmap

fn sub(self, rhs: RoaringBitmap) -> RoaringBitmap

A difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the - operator.

impl Sub for RoaringBitmap

fn sub(self, rhs: RoaringBitmap) -> RoaringBitmap

A difference between two sets.

type Output = RoaringBitmap

The resulting type after applying the - operator.

impl SubAssign<&RoaringBitmap> for RoaringBitmap

fn sub_assign(&mut self, rhs: &RoaringBitmap)

A difference between two sets.

impl SubAssign for RoaringBitmap

fn sub_assign(&mut self, rhs: RoaringBitmap)

A difference between two sets.

impl StructuralPartialEq for RoaringBitmap