roaring/
lib.rs

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

roaring/
lib.rs
