Struct roaring::treemap::RoaringTreemap

pub struct RoaringTreemap { /* private fields */ }

A compressed bitmap with u64 values. Implemented as a BTreeMap of RoaringBitmaps.

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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 RoaringTreemap

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::RoaringTreemap;

let mut rb1 = RoaringTreemap::new();
let mut rb2 = RoaringTreemap::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::RoaringTreemap;

let mut rb1 = RoaringTreemap::new();
let mut rb2 = RoaringTreemap::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::RoaringTreemap;

let mut rb1 = RoaringTreemap::new();
let mut rb2 = RoaringTreemap::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 RoaringTreemap

pub fn new() -> RoaringTreemap

Creates an empty RoaringTreemap.

Examples

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

pub fn full() -> RoaringTreemap

Creates a full RoaringTreemap.

Examples

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

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

Adds a value to the set. Returns true if the value was not already present in the set.

Examples

use roaring::RoaringTreemap;

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

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

Inserts a range of values.

Returns the number of inserted values.

Examples

use roaring::RoaringTreemap;

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

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

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

Returns whether the value was inserted.

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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<u64>>(), vec![1, 3, 5]);

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

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

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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<u64>,

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

Examples

use roaring::RoaringTreemap;

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

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

Returns true if this set contains the specified integer.

Examples

use roaring::RoaringTreemap;

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

pub fn clear(&mut self)

Clears all integers in this set.

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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::RoaringTreemap;

let mut rb = RoaringTreemap::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::RoaringTreemap;

let mut rb = RoaringTreemap::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::RoaringTreemap;

let mut rb = RoaringTreemap::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<u64>

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

Examples

use roaring::RoaringTreemap;

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

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

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

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

Examples

use roaring::RoaringTreemap;

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

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

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

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

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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: u64) -> Option<u64>

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

Examples

use roaring::RoaringTreemap;

let mut rb = RoaringTreemap::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);

impl RoaringTreemap

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

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

Examples

use roaring::RoaringTreemap;
use core::iter::FromIterator;

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

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

pub fn bitmaps(&self) -> BitmapIter<'_>

Iterator over pairs of partition number and the corresponding RoaringBitmap. The partition number is defined by the 32 most significant bits of the bit index.

Examples

use roaring::{RoaringBitmap, RoaringTreemap};
use core::iter::FromIterator;

let original = (0..6000).collect::<RoaringTreemap>();
let mut bitmaps = original.bitmaps();

assert_eq!(bitmaps.next(), Some((0, &(0..6000).collect::<RoaringBitmap>())));
assert_eq!(bitmaps.next(), None);

pub fn from_bitmaps<I: IntoIterator<Item = (u32, RoaringBitmap)>>( iterator: I ) -> Self

Construct a RoaringTreemap from an iterator of partition number and RoaringBitmap pairs. The partition number is defined by the 32 most significant bits of the bit index. Note that repeated partitions, if present, will replace previously set partitions.

Examples

use roaring::RoaringTreemap;
use core::iter::FromIterator;

let original = (0..6000).collect::<RoaringTreemap>();
let clone = RoaringTreemap::from_bitmaps(original.bitmaps().map(|(p, b)| (p, b.clone())));

assert_eq!(clone, original);

impl RoaringTreemap

pub fn from_sorted_iter<I: IntoIterator<Item = u64>>( iterator: I ) -> Result<RoaringTreemap, 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 RoaringTreemap, Err with the number of elements we tried to append before an error occurred.

Examples

use roaring::RoaringTreemap;

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

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

pub fn append<I: IntoIterator<Item = u64>>( &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::RoaringTreemap;

let mut rb = RoaringTreemap::new();
rb.append(0..10);

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

impl RoaringTreemap

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

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

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

Examples

use roaring::RoaringTreemap;

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


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

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

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

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

Examples

use roaring::RoaringTreemap;

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


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

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

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

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

Examples

use roaring::RoaringTreemap;

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


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

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

Computes the len of the symmetric difference with the specified other treemap 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::RoaringTreemap;

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


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

impl RoaringTreemap

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::RoaringTreemap;

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

assert_eq!(rb1, rb2);

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

Serialize this bitmap. This is compatible with the official C/C++, Java and Go implementations.

Examples

use roaring::RoaringTreemap;

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

assert_eq!(rb1, rb2);

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

Deserialize a bitmap into memory.

This is compatible with the official C/C++, Java and Go implementations. This method checks that all of the internal values are valid.

Examples

use roaring::RoaringTreemap;

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

assert_eq!(rb1, rb2);

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

Deserialize a bitmap into memory.

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::RoaringTreemap;

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

assert_eq!(rb1, rb2);

Trait Implementations

impl BitAnd<&RoaringTreemap> for &RoaringTreemap

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

An intersection between two sets.

type Output = RoaringTreemap

The resulting type after applying the & operator.

impl BitAnd<&RoaringTreemap> for RoaringTreemap

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

An intersection between two sets.

type Output = RoaringTreemap

The resulting type after applying the & operator.

impl BitAnd<RoaringTreemap> for &RoaringTreemap

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

An intersection between two sets.

type Output = RoaringTreemap

The resulting type after applying the & operator.

impl BitAnd for RoaringTreemap

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

An intersection between two sets.

type Output = RoaringTreemap

The resulting type after applying the & operator.

impl BitAndAssign<&RoaringTreemap> for RoaringTreemap

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

An intersection between two sets.

impl BitAndAssign for RoaringTreemap

fn bitand_assign(&mut self, rhs: RoaringTreemap)

An intersection between two sets.

impl BitOr<&RoaringTreemap> for &RoaringTreemap

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

An union between two sets.

type Output = RoaringTreemap

The resulting type after applying the | operator.

impl BitOr<&RoaringTreemap> for RoaringTreemap

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

An union between two sets.

type Output = RoaringTreemap

The resulting type after applying the | operator.

impl BitOr<RoaringTreemap> for &RoaringTreemap

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

An union between two sets.

type Output = RoaringTreemap

The resulting type after applying the | operator.

impl BitOr for RoaringTreemap

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

An union between two sets.

type Output = RoaringTreemap

The resulting type after applying the | operator.

impl BitOrAssign<&RoaringTreemap> for RoaringTreemap

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

An union between two sets.

impl BitOrAssign for RoaringTreemap

fn bitor_assign(&mut self, rhs: RoaringTreemap)

An union between two sets.

impl BitXor<&RoaringTreemap> for &RoaringTreemap

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

A symmetric difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the ^ operator.

impl BitXor<&RoaringTreemap> for RoaringTreemap

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

A symmetric difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the ^ operator.

impl BitXor<RoaringTreemap> for &RoaringTreemap

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

A symmetric difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the ^ operator.

impl BitXor for RoaringTreemap

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

A symmetric difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the ^ operator.

impl BitXorAssign<&RoaringTreemap> for RoaringTreemap

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

A symmetric difference between two sets.

impl BitXorAssign for RoaringTreemap

fn bitxor_assign(&mut self, rhs: RoaringTreemap)

A symmetric difference between two sets.

impl Clone for RoaringTreemap

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 RoaringTreemap

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

Formats the value using the given formatter.

impl Default for RoaringTreemap

fn default() -> RoaringTreemap

Returns the “default value” for a type.

impl<'a> Extend<&'a u64> for RoaringTreemap

fn extend<I: IntoIterator<Item = &'a u64>>(&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<u64> for RoaringTreemap

fn extend<I: IntoIterator<Item = u64>>(&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<[u64; N]> for RoaringTreemap

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

Converts to this type from the input type.

impl<'a> FromIterator<&'a u64> for RoaringTreemap

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

Creates a value from an iterator.

impl FromIterator<(u32, RoaringBitmap)> for RoaringTreemap

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

Creates a value from an iterator.

impl FromIterator<u64> for RoaringTreemap

fn from_iter<I: IntoIterator<Item = u64>>(iterator: I) -> RoaringTreemap

Creates a value from an iterator.

impl<'a> IntoIterator for &'a RoaringTreemap

type Item = u64

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 RoaringTreemap

type Item = u64

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 RoaringTreemap> for I

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

type Output = RoaringTreemap

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<RoaringTreemap> for I

where I: IntoIterator<Item = RoaringTreemap>,

type Output = RoaringTreemap

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 RoaringTreemap

fn eq(&self, other: &RoaringTreemap) -> 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<&RoaringTreemap> for &RoaringTreemap

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

A difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the - operator.

impl Sub<&RoaringTreemap> for RoaringTreemap

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

A difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the - operator.

impl Sub<RoaringTreemap> for &RoaringTreemap

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

A difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the - operator.

impl Sub for RoaringTreemap

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

A difference between two sets.

type Output = RoaringTreemap

The resulting type after applying the - operator.

impl SubAssign<&RoaringTreemap> for RoaringTreemap

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

A difference between two sets.

impl SubAssign for RoaringTreemap

fn sub_assign(&mut self, rhs: RoaringTreemap)

A difference between two sets.

impl StructuralPartialEq for RoaringTreemap