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/// An error type that is returned when an iterator isn't sorted.
47#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
48pub struct NonSortedIntegers {
49    valid_until: u64,
50}
51
52impl NonSortedIntegers {
53    /// Returns the number of elements that were
54    pub fn valid_until(&self) -> u64 {
55        self.valid_until
56    }
57}
58
59impl fmt::Display for NonSortedIntegers {
60    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
61        write!(f, "integers are ordered up to the {}th element", self.valid_until())
62    }
63}
64
65#[cfg(feature = "std")]
66impl std::error::Error for NonSortedIntegers {}
67
68/// A [`Iterator::collect`] blanket implementation that provides extra methods for [`RoaringBitmap`]
69/// and [`RoaringTreemap`].
70///
71/// When merging multiple bitmap with the same operation it's usually faster to call the
72/// method in this trait than to write your own for loop and merging the bitmaps yourself.
73///
74/// # Examples
75/// ```
76/// use roaring::{MultiOps, RoaringBitmap};
77///
78/// let bitmaps = [
79///     RoaringBitmap::from_iter(0..10),
80///     RoaringBitmap::from_iter(10..20),
81///     RoaringBitmap::from_iter(20..30),
82/// ];
83///
84/// // Stop doing this
85/// let naive = bitmaps.clone().into_iter().reduce(|a, b| a | b).unwrap_or_default();
86///
87/// // And start doing this instead, it will be much faster!
88/// let iter = bitmaps.union();
89///
90/// assert_eq!(naive, iter);
91/// ```
92pub trait MultiOps<T>: IntoIterator<Item = T> {
93    /// The type of output from operations.
94    type Output;
95
96    /// The `union` between all elements.
97    fn union(self) -> Self::Output;
98
99    /// The `intersection` between all elements.
100    fn intersection(self) -> Self::Output;
101
102    /// The `difference` between all elements.
103    fn difference(self) -> Self::Output;
104
105    /// The `symmetric difference` between all elements.
106    fn symmetric_difference(self) -> Self::Output;
107}
roaring/lib.rs

roaring/
lib.rs
