[][src]Struct hibitset::BitSet

pub struct BitSet { /* fields omitted */ }

A BitSet is a simple set designed to track which indices are placed into it.

Note, a BitSet is limited by design to only usize**4 indices. Adding beyond this limit will cause the BitSet to panic.

Methods

impl BitSet[src]

pub fn new() -> BitSet[src]

Creates an empty BitSet.

pub fn with_capacity(max: u32) -> BitSet[src]

Creates an empty BitSet, preallocated for up to max indices.

pub fn add(&mut self, id: u32) -> bool[src]

Adds id to the BitSet. Returns true if the value was already in the set.

pub fn remove(&mut self, id: u32) -> bool[src]

Removes id from the set, returns true if the value was removed, and false if the value was not set to begin with.

pub fn contains(&self, id: u32) -> bool[src]

Returns true if id is in the set.

pub fn contains_set(&self, other: &BitSet) -> bool[src]

Returns true if all ids in other are contained in this set

pub fn clear(&mut self)[src]

Completely wipes out the bit set.

pub const BITS_PER_USIZE: usize[src]

How many bits are in a usize.

This value can be trivially determined. It is provided here as a constant for clarity.

Example

use hibitset::BitSet;
assert_eq!(BitSet::BITS_PER_USIZE, std::mem::size_of::<usize>()*8);

pub fn layer0_as_slice(&self) -> &[usize][src]

Returns the bottom layer of the bitset as a slice. Each bit in this slice refers to a single Index.

The slice's length will be at least the length needed to reflect all the 1s in the bitset, but is not otherwise guaranteed. Consider it to be an implementation detail.

Example

use hibitset::BitSet;

let index: u32 = 12345;

let mut bitset = BitSet::new();
bitset.add(index);

// layer 0 is 1:1 with Indexes, so we expect that bit in the slice to be set
let slice = bitset.layer0_as_slice();
let bit_index = index as usize;

// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;

assert_eq!(slice[slice_index], 1 << bit_at_index);

pub const LAYER1_GRANULARITY: usize[src]

How many Indexes are described by as single layer 1 bit, intended for use with BitSet::layer1_as_slice().

BitSets are defined in terms of usizes summarizing usizes, so this value can be trivially determined. It is provided here as a constant for clarity.

Example

use hibitset::BitSet;
assert_eq!(BitSet::LAYER1_GRANULARITY, BitSet::BITS_PER_USIZE);

pub fn layer1_as_slice(&self) -> &[usize][src]

Returns the second layer of the bitset as a slice. Each bit in this slice summarizes a corresponding usize from layer0. (If usize is 64 bits, bit 0 will be set if any Indexes 0-63 are set, bit 1 will be set if any Indexes 64-127 are set, etc.) BitSet::LAYER1_GRANULARITY reflects how many indexes are summarized per layer 1 bit.

The slice's length is not guaranteed, except that it will be at least the length needed to reflect all the 1s in the bitset.

Example

use hibitset::BitSet;

let index: u32 = 12345;

let mut bitset = BitSet::new();
bitset.add(index);

// layer 1 summarizes multiple indexes per bit, so divide appropriately
let slice = bitset.layer1_as_slice();
let bit_index = index as usize / BitSet::LAYER1_GRANULARITY;

// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;

assert_eq!(slice[slice_index], 1 << bit_at_index);

pub const LAYER2_GRANULARITY: usize[src]

How many Indexes are described by as single layer 2 bit, intended for use with BitSet::layer2_as_slice().

BitSets are defined in terms of usizes summarizing usizes, so this value can be trivially determined. It is provided here as a constant for clarity.

Example

use hibitset::BitSet;
assert_eq!(BitSet::LAYER2_GRANULARITY, BitSet::LAYER1_GRANULARITY * BitSet::BITS_PER_USIZE);

pub fn layer2_as_slice(&self) -> &[usize][src]

Returns the third layer of the bitset as a slice. Each bit in this slice summarizes a corresponding usize from layer1. If usize is 64 bits, bit 0 will be set if any Indexes 0-4095 are set, bit 1 will be set if any Indexes 4096-8191 are set, etc.

The slice's length is not guaranteed, except that it will be at least the length needed to reflect all the 1s in the bitset.

Example

use hibitset::BitSet;

let index: u32 = 12345;

let mut bitset = BitSet::new();
bitset.add(index);

// layer 2 summarizes multiple indexes per bit, so divide appropriately
let slice = bitset.layer2_as_slice();
let bit_index = index as usize / BitSet::LAYER2_GRANULARITY;

// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;

assert_eq!(slice[slice_index], 1 << bit_at_index);

Trait Implementations

impl<T> BitAnd<T> for BitSet where
    T: BitSetLike
[src]

type Output = BitSetAnd<Self, T>

The resulting type after applying the & operator.

impl<'a, T> BitAnd<T> for &'a BitSet where
    T: BitSetLike
[src]

type Output = BitSetAnd<Self, T>

The resulting type after applying the & operator.

impl<'a, B> BitAndAssign<&'a B> for BitSet where
    B: BitSetLike
[src]

impl<T> BitOr<T> for BitSet where
    T: BitSetLike
[src]

type Output = BitSetOr<Self, T>

The resulting type after applying the | operator.

impl<'a, T> BitOr<T> for &'a BitSet where
    T: BitSetLike
[src]

type Output = BitSetOr<Self, T>

The resulting type after applying the | operator.

impl<'a, B> BitOrAssign<&'a B> for BitSet where
    B: BitSetLike
[src]

impl BitSetLike for BitSet[src]

impl<T> BitXor<T> for BitSet where
    T: BitSetLike
[src]

type Output = BitSetXor<Self, T>

The resulting type after applying the ^ operator.

impl<'a, T> BitXor<T> for &'a BitSet where
    T: BitSetLike
[src]

type Output = BitSetXor<Self, T>

The resulting type after applying the ^ operator.

impl<'a, B> BitXorAssign<&'a B> for BitSet where
    B: BitSetLike
[src]

impl Clone for BitSet[src]

impl Debug for BitSet[src]

impl Default for BitSet[src]

impl DrainableBitSet for BitSet[src]

impl Eq for BitSet[src]

impl<'a> Extend<&'a u32> for BitSet[src]

impl Extend<u32> for BitSet[src]

impl<'a> FromIterator<&'a u32> for BitSet[src]

impl FromIterator<u32> for BitSet[src]

impl IntoIterator for BitSet[src]

type Item = <BitIter<Self> as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = BitIter<Self>

Which kind of iterator are we turning this into?

impl<'a> IntoIterator for &'a BitSet[src]

type Item = <BitIter<Self> as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = BitIter<Self>

Which kind of iterator are we turning this into?

impl Not for BitSet[src]

type Output = BitSetNot<Self>

The resulting type after applying the ! operator.

impl<'a> Not for &'a BitSet[src]

type Output = BitSetNot<Self>

The resulting type after applying the ! operator.

impl PartialEq<BitSet> for BitSet[src]

Auto Trait Implementations

impl RefUnwindSafe for BitSet

impl Send for BitSet

impl Sync for BitSet

impl Unpin for BitSet

impl UnwindSafe for BitSet

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<I> IntoIterator for I where
    I: Iterator
[src]

type Item = <I as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = I

Which kind of iterator are we turning this into?

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.