1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
//! This is a [Rust][] port of the [Roaring bitmap][] data structure, initially
//! defined as a [Java library][roaring-java] and described in [_Better bitmap
//! performance with Roaring bitmaps_][roaring-paper].
//!
//! [Rust]: https://www.rust-lang.org/
//! [Roaring bitmap]: https://roaringbitmap.org/
//! [roaring-java]: https://github.com/lemire/RoaringBitmap
//! [roaring-paper]: https://arxiv.org/pdf/1402.6407v4
#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(feature = "simd", feature(portable_simd))]
#![warn(missing_docs)]
#![warn(unsafe_op_in_unsafe_fn)]
#![warn(variant_size_differences)]
#![allow(unknown_lints)] // For clippy
#[cfg(feature = "std")]
extern crate byteorder;
#[macro_use]
extern crate alloc;
use core::fmt;
/// A compressed bitmap using the [Roaring bitmap compression scheme](https://roaringbitmap.org/).
pub mod bitmap;
/// A compressed bitmap with u64 values. Implemented as a `BTreeMap` of `RoaringBitmap`s.
pub mod treemap;
pub use bitmap::RoaringBitmap;
pub use treemap::RoaringTreemap;
/// An error type that is returned when an iterator isn't sorted.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct NonSortedIntegers {
valid_until: u64,
}
impl NonSortedIntegers {
/// Returns the number of elements that were
pub fn valid_until(&self) -> u64 {
self.valid_until
}
}
impl fmt::Display for NonSortedIntegers {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "integers are ordered up to the {}th element", self.valid_until())
}
}
#[cfg(feature = "std")]
impl std::error::Error for NonSortedIntegers {}
/// A [`Iterator::collect`] blanket implementation that provides extra methods for [`RoaringBitmap`]
/// and [`RoaringTreemap`].
///
/// When merging multiple bitmap with the same operation it's usually faster to call the
/// method in this trait than to write your own for loop and merging the bitmaps yourself.
///
/// # Examples
/// ```
/// use roaring::{MultiOps, RoaringBitmap};
///
/// let bitmaps = [
/// RoaringBitmap::from_iter(0..10),
/// RoaringBitmap::from_iter(10..20),
/// RoaringBitmap::from_iter(20..30),
/// ];
///
/// // Stop doing this
/// let naive = bitmaps.clone().into_iter().reduce(|a, b| a | b).unwrap_or_default();
///
/// // And start doing this instead, it will be much faster!
/// let iter = bitmaps.union();
///
/// assert_eq!(naive, iter);
/// ```
pub trait MultiOps<T>: IntoIterator<Item = T> {
/// The type of output from operations.
type Output;
/// The `union` between all elements.
fn union(self) -> Self::Output;
/// The `intersection` between all elements.
fn intersection(self) -> Self::Output;
/// The `difference` between all elements.
fn difference(self) -> Self::Output;
/// The `symmetric difference` between all elements.
fn symmetric_difference(self) -> Self::Output;
}