Source code
Revision control
Copy as Markdown
Other Tools
use crate::{local_prelude::*, util};
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
#[cfg_attr(
feature = "borsh",
derive(borsh::BorshDeserialize, borsh::BorshSerialize)
)]
#[cfg_attr(
feature = "miniserde",
derive(miniserde::Deserialize, miniserde::Serialize)
)]
pub struct BitSet<B: BitBlock = u32> {
pub(crate) bit_vec: BitVec<B>,
}
impl<B: BitBlock> Clone for BitSet<B> {
fn clone(&self) -> Self {
BitSet {
bit_vec: self.bit_vec.clone(),
}
}
fn clone_from(&mut self, other: &Self) {
self.bit_vec.clone_from(&other.bit_vec);
}
}
impl<B: BitBlock> Default for BitSet<B> {
#[inline]
fn default() -> Self {
BitSet {
bit_vec: Default::default(),
}
}
}
impl<B: BitBlock> FromIterator<usize> for BitSet<B> {
fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
let mut ret = Self::default();
ret.extend(iter);
ret
}
}
impl<B: BitBlock> Extend<usize> for BitSet<B> {
#[inline]
fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
for i in iter {
self.insert(i);
}
}
}
impl<B: BitBlock> PartialOrd for BitSet<B> {
#[inline]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<B: BitBlock> Ord for BitSet<B> {
#[inline]
fn cmp(&self, other: &Self) -> Ordering {
self.iter().cmp(other)
}
}
impl<B: BitBlock> PartialEq for BitSet<B> {
#[inline]
fn eq(&self, other: &Self) -> bool {
self.iter().eq(other)
}
}
impl<B: BitBlock> Eq for BitSet<B> {}
impl BitSet<u32> {
/// Creates a new empty `BitSet`.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::new();
/// ```
#[inline]
pub fn new() -> Self {
Self::default()
}
/// Creates a new `BitSet` with initially no contents, able to
/// hold `nbits` elements without resizing.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::with_capacity(100);
/// assert!(s.capacity() >= 100);
/// ```
#[inline]
pub fn with_capacity(nbits: usize) -> Self {
let bit_vec = BitVec::from_elem(nbits, false);
Self::from_bit_vec(bit_vec)
}
/// Creates a new `BitSet` from the given bit vector.
///
/// # Examples
///
/// ```
/// use bit_vec::BitVec;
/// use bit_set::BitSet;
///
/// let bv = BitVec::from_bytes(&[0b01100000]);
/// let s = BitSet::from_bit_vec(bv);
///
/// // Print 1, 2 in arbitrary order
/// for x in s.iter() {
/// println!("{}", x);
/// }
/// ```
#[inline]
pub fn from_bit_vec(bit_vec: BitVec) -> Self {
BitSet { bit_vec }
}
pub fn from_bytes(bytes: &[u8]) -> Self {
BitSet {
bit_vec: BitVec::from_bytes(bytes),
}
}
}
#[allow(clippy::multiple_inherent_impl)]
impl<B: BitBlock> BitSet<B> {
/// Creates a new empty `BitSet`.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = <BitSet>::new_general();
/// ```
#[inline]
pub fn new_general() -> Self {
Self::default()
}
/// Creates a new `BitSet` with initially no contents, able to
/// hold `nbits` elements without resizing.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = <BitSet>::with_capacity_general(100);
/// assert!(s.capacity() >= 100);
/// ```
#[inline]
pub fn with_capacity_general(nbits: usize) -> Self {
let bit_vec = BitVec::from_elem_general(nbits, false);
Self::from_bit_vec_general(bit_vec)
}
/// Creates a new `BitSet` from the given bit vector.
///
/// # Examples
///
/// ```
/// use bit_vec::BitVec;
/// use bit_set::BitSet;
///
/// let bv: BitVec<u64> = BitVec::from_bytes_general(&[0b01100000]);
/// let s = BitSet::from_bit_vec_general(bv);
///
/// // Print 1, 2 in arbitrary order
/// for x in s.iter() {
/// println!("{}", x);
/// }
/// ```
#[inline]
pub fn from_bit_vec_general(bit_vec: BitVec<B>) -> Self {
BitSet { bit_vec }
}
pub fn from_bytes_general(bytes: &[u8]) -> Self {
BitSet {
bit_vec: BitVec::from_bytes_general(bytes),
}
}
/// Returns the capacity in bits for this bit vector. Inserting any
/// element less than this amount will not trigger a resizing.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::with_capacity(100);
/// assert!(s.capacity() >= 100);
/// ```
#[inline]
pub fn capacity(&self) -> usize {
self.bit_vec.capacity()
}
/// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
/// of `BitSet` this means reallocations will not occur as long as all inserted elements
/// are less than `len`.
///
/// The collection may reserve more space to avoid frequent reallocations.
///
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::new();
/// s.reserve_len(10);
/// assert!(s.capacity() >= 10);
/// ```
pub fn reserve_len(&mut self, len: usize) {
let cur_len = self.bit_vec.len();
if len >= cur_len {
self.bit_vec.reserve(len - cur_len);
}
}
/// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
/// In the case of `BitSet` this means reallocations will not occur as long as all inserted
/// elements are less than `len`.
///
/// Note that the allocator may give the collection more space than it requests. Therefore
/// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
/// insertions are expected.
///
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::new();
/// s.reserve_len_exact(10);
/// assert!(s.capacity() >= 10);
/// ```
pub fn reserve_len_exact(&mut self, len: usize) {
let cur_len = self.bit_vec.len();
if len >= cur_len {
self.bit_vec.reserve_exact(len - cur_len);
}
}
/// Consumes this set to return the underlying bit vector.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::new();
/// s.insert(0);
/// s.insert(3);
///
/// let bv = s.into_bit_vec();
/// assert!(bv[0]);
/// assert!(bv[3]);
/// ```
#[inline]
pub fn into_bit_vec(self) -> BitVec<B> {
self.bit_vec
}
/// Returns a reference to the underlying bit vector.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut set = BitSet::new();
/// set.insert(0);
///
/// let bv = set.get_ref();
/// assert_eq!(bv[0], true);
/// ```
#[inline]
pub fn get_ref(&self) -> &BitVec<B> {
&self.bit_vec
}
/// Returns a mutable reference to the underlying bit vector.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut set = BitSet::new();
/// set.insert(0);
/// set.insert(3);
///
/// {
/// let bv = set.get_mut();
/// bv.set(1, true);
/// }
///
/// assert!(set.contains(0));
/// assert!(set.contains(1));
/// assert!(set.contains(3));
/// ```
#[inline]
pub fn get_mut(&mut self) -> &mut BitVec<B> {
&mut self.bit_vec
}
/// # Safety
///
/// Safe and upholds invariant if function `f` does not alter most
/// significant bits of the first argument where respective bits
/// in the second argument are equal 0.
///
/// In other words, this is safe if `f` is XOR, OR, AND, but violates
/// invariant if it is XNOR, NAND.
///
/// See the safety section below.
#[inline]
fn other_op<F>(&mut self, other: &Self, mut f: F)
where
F: FnMut(B, B) -> B,
{
// Unwrap BitVecs
let self_bit_vec = &mut self.bit_vec;
let other_bit_vec = &other.bit_vec;
let self_len = self_bit_vec.len();
let other_len = other_bit_vec.len();
// Expand the vector if necessary
if self_len < other_len {
self_bit_vec.grow(other_len - self_len, false);
}
// virtually pad other with 0's for equal lengths
let other_words = util::match_words(self_bit_vec, other_bit_vec).1;
debug_assert!(self_bit_vec.len() >= other_bit_vec.len());
// Apply values found in other
for (i, w) in other_words {
let old = self_bit_vec.storage()[i];
let new = f(old, w);
// Safety:
// We do not change the underlying Vec's size, so this is always ok.
// - What do we do to uphold the invariant for trailing bits?
// - We have a debug assert below that guards us against polluting
// trailing bits.
unsafe {
self_bit_vec.storage_mut()[i] = new;
}
if i == self_bit_vec.storage().len() - 1 && self_bit_vec.len() % B::bits() > 0 {
debug_assert!(new >> (self_bit_vec.len() % B::bits()) == B::zero());
}
}
}
/// Truncates the underlying vector to the least length required.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut s = BitSet::new();
/// s.insert(3231);
/// s.remove(3231);
///
/// // Internal storage will probably be bigger than necessary
/// println!("old capacity: {}", s.capacity());
/// assert!(s.capacity() >= 3231);
///
/// // Now should be smaller
/// s.shrink_to_fit();
/// println!("new capacity: {}", s.capacity());
/// ```
#[inline]
pub fn shrink_to_fit(&mut self) {
let bit_vec = &mut self.bit_vec;
// Obtain original length
let old_len = bit_vec.storage().len();
// Obtain coarse trailing zero length
let n = bit_vec
.storage()
.iter()
.rev()
.take_while(|&&n| n == B::zero())
.count();
// Truncate away all empty trailing blocks, then shrink_to_fit
let trunc_len = old_len - n;
// Safety:
// Those function calls may seem unsafe, but they are guaranteed
// not to introduce any memory unsafety.
// We set the correct length as a multiple of `B::bits()`,
// thus maintaining the trailing bit invariant.
unsafe {
bit_vec.storage_mut().truncate(trunc_len);
bit_vec.set_len(trunc_len * B::bits());
}
bit_vec.shrink_to_fit();
}
/// Unions in-place with the specified other bit vector.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let a = 0b01101000;
/// let b = 0b10100000;
/// let res = 0b11101000;
///
/// let mut a = BitSet::from_bytes(&[a]);
/// let b = BitSet::from_bytes(&[b]);
/// let res = BitSet::from_bytes(&[res]);
///
/// a.union_with(&b);
/// assert_eq!(a, res);
/// ```
#[inline]
pub fn union_with(&mut self, other: &Self) {
self.other_op(other, |w1, w2| w1 | w2);
}
/// Intersects in-place with the specified other bit vector.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let a = 0b01101000;
/// let b = 0b10100000;
/// let res = 0b00100000;
///
/// let mut a = BitSet::from_bytes(&[a]);
/// let b = BitSet::from_bytes(&[b]);
/// let res = BitSet::from_bytes(&[res]);
///
/// a.intersect_with(&b);
/// assert_eq!(a, res);
/// ```
#[inline]
pub fn intersect_with(&mut self, other: &Self) {
self.other_op(other, |w1, w2| w1 & w2);
}
/// Makes this bit vector the difference with the specified other bit vector
/// in-place.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let a = 0b01101000;
/// let b = 0b10100000;
/// let a_b = 0b01001000; // a - b
/// let b_a = 0b10000000; // b - a
///
/// let mut bva = BitSet::from_bytes(&[a]);
/// let bvb = BitSet::from_bytes(&[b]);
/// let bva_b = BitSet::from_bytes(&[a_b]);
/// let bvb_a = BitSet::from_bytes(&[b_a]);
///
/// bva.difference_with(&bvb);
/// assert_eq!(bva, bva_b);
///
/// let bva = BitSet::from_bytes(&[a]);
/// let mut bvb = BitSet::from_bytes(&[b]);
///
/// bvb.difference_with(&bva);
/// assert_eq!(bvb, bvb_a);
/// ```
#[inline]
pub fn difference_with(&mut self, other: &Self) {
self.other_op(other, |w1, w2| w1 & !w2);
}
/// Makes this bit vector the symmetric difference with the specified other
/// bit vector in-place.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let a = 0b01101000;
/// let b = 0b10100000;
/// let res = 0b11001000;
///
/// let mut a = BitSet::from_bytes(&[a]);
/// let b = BitSet::from_bytes(&[b]);
/// let res = BitSet::from_bytes(&[res]);
///
/// a.symmetric_difference_with(&b);
/// assert_eq!(a, res);
/// ```
#[inline]
pub fn symmetric_difference_with(&mut self, other: &Self) {
self.other_op(other, |w1, w2| w1 ^ w2);
}
/*
/// Moves all elements from `other` into `Self`, leaving `other` empty.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut a = BitSet::new();
/// a.insert(2);
/// a.insert(6);
///
/// let mut b = BitSet::new();
/// b.insert(1);
/// b.insert(3);
/// b.insert(6);
///
/// a.append(&mut b);
///
/// assert_eq!(a.len(), 4);
/// assert_eq!(b.len(), 0);
/// assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
/// ```
pub fn append(&mut self, other: &mut Self) {
self.union_with(other);
other.clear();
}
/// Splits the `BitSet` into two at the given key including the key.
/// Retains the first part in-place while returning the second part.
///
/// # Examples
///
/// ```
/// use bit_set::BitSet;
///
/// let mut a = BitSet::new();
/// a.insert(2);
/// a.insert(6);
/// a.insert(1);
/// a.insert(3);
///
/// let b = a.split_off(3);
///
/// assert_eq!(a.len(), 2);
/// assert_eq!(b.len(), 2);
/// assert_eq!(a, BitSet::from_bytes(&[0b01100000]));
/// assert_eq!(b, BitSet::from_bytes(&[0b00010010]));
/// ```
pub fn split_off(&mut self, at: usize) -> Self {
let mut other = BitSet::new();
if at == 0 {
swap(self, &mut other);
return other;
} else if at >= self.bit_vec.len() {
return other;
}
// Calculate block and bit at which to split
let w = at / BITS;
let b = at % BITS;
// Pad `other` with `w` zero blocks,
// append `self`'s blocks in the range from `w` to the end to `other`
other.bit_vec.storage_mut().extend(repeat(0u32).take(w)
.chain(self.bit_vec.storage()[w..].iter().cloned()));
other.bit_vec.nbits = self.bit_vec.nbits;
if b > 0 {
other.bit_vec.storage_mut()[w] &= !0 << b;
}
// Sets `bit_vec.len()` and fixes the last block as well
self.bit_vec.truncate(at);
other
}
*/
/// Counts the number of set bits in this set.
///
/// Note that this function scans the set to calculate the number.
#[inline]
pub fn count(&self) -> usize {
self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones())
}
/// Counts the number of set bits in this set.
///
/// Note that this function scans the set to calculate the number.
#[inline]
#[deprecated = "use BitVec::count() instead"]
pub fn len(&self) -> usize {
self.count()
}
/// Returns whether there are no bits set in this set
#[inline]
pub fn is_empty(&self) -> bool {
self.bit_vec.none()
}
/// Removes all elements of this set.
///
/// Different from [`reset`] only in that the capacity is preserved.
///
/// [`reset`]: Self::reset
#[inline]
pub fn make_empty(&mut self) {
self.bit_vec.fill(false);
}
/// Resets this set to an empty state.
///
/// Different from [`make_empty`] only in that the capacity may NOT be preserved.
///
/// [`make_empty`]: Self::make_empty
#[inline]
pub fn reset(&mut self) {
self.bit_vec.remove_all();
}
/// Clears all bits in this set
#[deprecated(since = "0.9.0", note = "please use `fn make_empty` instead")]
#[inline]
pub fn clear(&mut self) {
self.make_empty();
}
/// Returns `true` if this set contains the specified integer.
#[inline]
pub fn contains(&self, value: usize) -> bool {
let bit_vec = &self.bit_vec;
value < bit_vec.len() && bit_vec[value]
}
/// Returns `true` if the set has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
#[inline]
pub fn is_disjoint(&self, other: &Self) -> bool {
self.intersection(other).next().is_none()
}
/// Returns `true` if the set is a subset of another.
#[inline]
pub fn is_subset(&self, other: &Self) -> bool {
let self_bit_vec = &self.bit_vec;
let other_bit_vec = &other.bit_vec;
let other_blocks = util::blocks_for_bits::<B>(other_bit_vec.len());
// Check that `self` intersect `other` is self
self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
// Make sure if `self` has any more blocks than `other`, they're all 0
self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
}
/// Returns `true` if the set is a superset of another.
#[inline]
pub fn is_superset(&self, other: &Self) -> bool {
other.is_subset(self)
}
/// Adds a value to the set. Returns `true` if the value was not already
/// present in the set.
pub fn insert(&mut self, value: usize) -> bool {
if self.contains(value) {
return false;
}
// Ensure we have enough space to hold the new element
let len = self.bit_vec.len();
if value >= len {
self.bit_vec.grow(value - len + 1, false);
}
self.bit_vec.set(value, true);
true
}
/// Removes a value from the set. Returns `true` if the value was
/// present in the set.
pub fn remove(&mut self, value: usize) -> bool {
if !self.contains(value) {
return false;
}
self.bit_vec.set(value, false);
true
}
/// Excludes `element` and all greater elements from the `BitSet`.
pub fn truncate(&mut self, element: usize) {
self.bit_vec.truncate(element);
}
}
impl<B: BitBlock> fmt::Debug for BitSet<B> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
fmt.debug_struct("BitSet")
.field("bit_vec", &self.bit_vec)
.finish()
}
}
impl<B: BitBlock> fmt::Display for BitSet<B> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
fmt.debug_set().entries(self).finish()
}
}
impl<B: BitBlock> hash::Hash for BitSet<B> {
fn hash<H: hash::Hasher>(&self, state: &mut H) {
for pos in self {
pos.hash(state);
}
}
}