Struct unicycle::BitSet

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

A sparse, layered bit set.

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

BitSet and AtomicBitSet's are guaranteed to have an identical memory layout, so while it would require unsafe, transmuting or coercing between the two is sound assuming the proper synchronization is respected.

A BitSet provides the following methods for converting to an AtomicBitSet: into_atomic and as_atomic.

Methods

impl BitSet

pub fn new() -> Self

Construct a new, empty BitSet with an empty capacity.

Examples

use unicycle::BitSet;

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

pub fn with_capacity(capacity: usize) -> Self

Construct a new, empty BitSet with the specified capacity.

Examples

use unicycle::BitSet;

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

pub fn is_empty(&self) -> bool

Test if the bit set is empty.

Examples

use unicycle::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());

pub fn capacity(&self) -> usize

Get the current capacity of the bitset.

Examples

use unicycle::BitSet;

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

pub fn layers(&self) -> Vec<&[usize]>

Return a view of the underlying, raw layers.

Examples

use unicycle::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.layers());

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 unicycle::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));

pub fn as_atomic(&self) -> &AtomicBitSet

Convert in-place into a reference to an AtomicBitSet.

Examples

use unicycle::BitSet;

let set = BitSet::with_capacity(1024);

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

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

Set the given bit.

Examples

use unicycle::BitSet;

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

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

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 unicycle::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());

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

Test if the given position is set.

Examples

use unicycle::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));

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 unicycle::BitSet;
let mut set = BitSet::with_capacity(128);
assert_eq!(128, set.capacity());
set.reserve(250);
assert_eq!(256, set.capacity());

Important traits for Drain<'_>

impl<'_> Iterator for Drain<'_> type Item = usize;

pub fn drain(&mut self) -> Drain

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

Examples

use unicycle::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 unicycle::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 unicycle::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());

Important traits for Drain<'_>

impl<'_> Iterator for Drain<'_> type Item = usize;

pub fn drain_from(&mut self, DrainSnapshot: DrainSnapshot) -> Drain

Start a drain operation using the given configuration parameters.

These are usually acquired from [Drain::save], and can be used to resume draining at a specific point.

Important traits for Iter<'_>

impl<'_> Iterator for Iter<'_> type Item = usize;

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 unicycle::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());

Trait Implementations

impl Clone for BitSet

fn clone(&self) -> BitSet

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for BitSet

fn default() -> Self

Returns the "default value" for a type.