indexical/bitset/
mod.rs

1//! Abstraction over bit-set implementations.
2
3/// Interface for bit-set implementations.
4///
5/// Implement this trait if you want to provide a custom bit-set
6/// beneath the indexical abstractions.
7pub trait BitSet: Clone + PartialEq {
8    /// Constructs a new bit-set with a domain of size `size`.
9    fn empty(size: usize) -> Self;
10
11    /// Sets `index` to 1, returning true if `self` changed.
12    fn insert(&mut self, index: usize) -> bool;
13
14    /// Sets `index` to 0, returning true if `self` changed.
15    fn remove(&mut self, index: usize) -> bool;
16
17    /// Returns true if `index` is 1.
18    fn contains(&self, index: usize) -> bool;
19
20    /// Returns an iterator over all the indices of ones in the bit-set.
21    fn iter(&self) -> impl Iterator<Item = usize>;
22
23    /// Returns the number of ones in the bit-set.
24    fn len(&self) -> usize;
25
26    /// Returns true if there are no ones in the bit-set.
27    fn is_empty(&self) -> bool {
28        self.len() == 0
29    }
30
31    // Note: we have the `_changed` methods separated out because
32    // if you don't care about the return value, then it's just extra
33    // computation w/ some APIs like bitvec.
34
35    /// Adds all ones from `other` to `self`.
36    fn union(&mut self, other: &Self);
37
38    /// Adds all ones from `other` to `self`, returning true if `self` changed.
39    fn union_changed(&mut self, other: &Self) -> bool {
40        let n = self.len();
41        self.union(other);
42        n != self.len()
43    }
44
45    /// Removes all ones in `self` not in `other`.
46    fn intersect(&mut self, other: &Self);
47
48    /// Removes all ones in `self` not in `other`, returning true if `self` changed.
49    fn intersect_changed(&mut self, other: &Self) -> bool {
50        let n = self.len();
51        self.intersect(other);
52        n != self.len()
53    }
54
55    /// Removes all ones from `other` in `self`.
56    fn subtract(&mut self, other: &Self);
57
58    /// Removes all ones from `other` in `self`, returning true if `self` changed.
59    fn subtract_changed(&mut self, other: &Self) -> bool {
60        let n = self.len();
61        self.intersect(other);
62        n != self.len()
63    }
64
65    /// Flips all bits in `self`.
66    fn invert(&mut self);
67
68    /// Sets all bits to 0.
69    fn clear(&mut self);
70
71    /// Adds every element of the domain to `self`.
72    fn insert_all(&mut self);
73
74    /// Returns true if all ones in `other` are a one in `self`.
75    fn superset(&self, other: &Self) -> bool {
76        let orig_len = self.len();
77        // TODO: can we avoid this clone?
78        let mut self_copy = self.clone();
79        self_copy.union(other);
80        orig_len == self_copy.len()
81    }
82
83    /// Copies `other` into `self`. Must have the same lengths.
84    fn copy_from(&mut self, other: &Self);
85}
86
87#[cfg(feature = "bitvec")]
88pub mod bitvec;
89
90#[cfg(feature = "rustc")]
91pub mod rustc;
92
93#[cfg(feature = "simd")]
94pub mod simd;
95
96#[cfg(feature = "roaring")]
97pub mod roaring;
indexical/bitset/mod.rs

indexical/bitset/
mod.rs
