Struct uniset::BitSet

source ·

#[repr(C)]
pub struct BitSet { /* private fields */ }

Expand description

A sparse, layered bit set.

Layered bit sets support efficient iteration, union, and intersection operations since they maintain summary layers of the bits which are set in layers below it.

BitSet and AtomicBitSet’s are guaranteed to have an identical memory layout, so they support zero-cost back and forth conversion.

The into_atomic and as_atomic methods are provided for converting to an AtomicBitSet.

Implementations§

source §

impl BitSet

source

pub fn new() -> Self

Construct a new, empty BitSet with an empty capacity.

§Examples

use uniset::BitSet;

let mut set = BitSet::new();
assert!(set.is_empty());
assert_eq!(0, set.capacity());

source

pub fn with_capacity(capacity: usize) -> Self

Construct a new, empty BitSet with the specified capacity.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(1024);
assert!(set.is_empty());
assert_eq!(1024, set.capacity());

source

pub fn is_empty(&self) -> bool

Test if the bit set is empty.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(64);
assert!(set.is_empty());
set.set(2);
assert!(!set.is_empty());
set.clear(2);
assert!(set.is_empty());

source

pub fn capacity(&self) -> usize

Get the current capacity of the bitset.

§Examples

use uniset::BitSet;

let mut set = BitSet::new();
assert!(set.is_empty());
assert_eq!(0, set.capacity());

source

pub fn as_slice(&self) -> &[Layer]

Return a slice of the underlying, raw layers.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);
set.set(1);
set.set(5);
// Note: two layers since we specified a capacity of 128.
assert_eq!(vec![&[0b100010, 0][..], &[1]], set.as_slice());

source

pub fn as_mut_slice(&mut self) -> &mut [Layer]

Return a mutable slice of the underlying, raw layers.

source

pub fn into_atomic(self) -> AtomicBitSet

Convert in-place into an AtomicBitSet.

Atomic bit sets uses structural sharing with the current set, so this is a constant time O(1) operation.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(1024);

let atomic = set.into_atomic();
atomic.set(42);

let set = atomic.into_local();
assert!(set.test(42));

source

pub fn as_atomic(&self) -> &AtomicBitSet

Convert in-place into a reference to an AtomicBitSet.

§Examples

use uniset::BitSet;

let set = BitSet::with_capacity(1024);

set.as_atomic().set(42);
assert!(set.test(42));

source

pub fn set(&mut self, position: usize)

Set the given bit.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(64);

assert!(set.is_empty());
set.set(2);
assert!(!set.is_empty());

source

pub fn clear(&mut self, position: usize)

Clear the given bit.

§Panics

Panics if the position does not fit within the capacity of the BitSet.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(64);

set.clear(2);
assert!(set.is_empty());
set.set(2);
assert!(!set.is_empty());
set.clear(2);
assert!(set.is_empty());
set.clear(2);
assert!(set.is_empty());

source

pub fn test(&self, position: usize) -> bool

Test if the given position is set.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(64);

assert!(set.is_empty());
set.set(2);
assert!(!set.is_empty());
assert!(set.test(2));
assert!(!set.test(3));

source

pub fn reserve(&mut self, cap: usize)

Reserve enough space to store the given number of elements.

This will not reserve space for exactly as many elements specified, but will round up to the closest order of magnitude of 2.

§Examples

use uniset::BitSet;
let mut set = BitSet::with_capacity(128);
assert_eq!(128, set.capacity());
set.reserve(250);
assert_eq!(256, set.capacity());

source

pub fn drain(&mut self) -> Drain<'_> ⓘ

Create a draining iterator over the bitset, yielding all elements in order of their index.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);
set.set(127);
set.set(32);
set.set(3);

assert_eq!(vec![3, 32, 127], set.drain().collect::<Vec<_>>());
assert!(set.is_empty());

Draining one bit at a time.

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);

set.set(127);
set.set(32);
set.set(3);

assert_eq!(Some(3), set.drain().next());
assert_eq!(Some(32), set.drain().next());
assert_eq!(Some(127), set.drain().next());
assert!(set.is_empty());

Saving the state of the draining iterator.

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);

set.set(127);
set.set(32);
set.set(3);

let mut it = set.drain();

assert_eq!(Some(3), it.next());
assert_eq!(Some(32), it.next());
assert!(it.snapshot().is_some());
assert_eq!(Some(127), it.next());
assert!(it.snapshot().is_none());
assert_eq!(None, it.next());
assert!(it.snapshot().is_none());

source

pub fn drain_from(&mut self, DrainSnapshot: DrainSnapshot) -> Drain<'_> ⓘ

Start a drain operation using the given configuration parameters.

These are acquired from Drain::snapshot, and can be used to resume draining at a specific point.

Resuming a drain from a snapshot can be more efficient in certain scenarios, like if the BitSet is very large.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);

set.set(127);
set.set(32);
set.set(3);

let mut it = set.drain();

assert_eq!(Some(3), it.next());
let snapshot = it.snapshot();
// Get rid of the existing iterator.
drop(it);

let snapshot = snapshot.expect("draining iteration hasn't ended");

let mut it = set.drain_from(snapshot);
assert_eq!(Some(32), it.next());
assert_eq!(Some(127), it.next());
assert_eq!(None, it.next());

Trying to snapshot from an empty draining iterator:

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);

set.set(3);

let mut it = set.drain();

assert!(it.snapshot().is_some());
assert_eq!(Some(3), it.next());
assert!(it.snapshot().is_none());

source

pub fn iter(&self) -> Iter<'_> ⓘ

Create an iterator over the bitset, yielding all elements in order of their index.

Note that iterator allocates a vector with a size matching the number of layers in the BitSet.

§Examples

use uniset::BitSet;

let mut set = BitSet::with_capacity(128);
set.set(127);
set.set(32);
set.set(3);

assert_eq!(vec![3, 32, 127], set.iter().collect::<Vec<_>>());
assert!(!set.is_empty());