Struct BitSet

pub struct BitSet<Conf: Config> { /* private fields */ }

Hierarchical sparse bitset.

Tri-level hierarchy. Highest uint it can hold is Level0BitBlock::size() * Level1BitBlock::size() * DataBitBlock::size().

Only the last level contains blocks of actual data. Empty(skipped) data blocks are not allocated.

Structure optimized for intersection speed. (Other inter-bitset operations are in fact fast too - but intersection has the lowest algorithmic complexity.) Insert/remove/contains is fast O(1) too.

Implementations

impl<Conf: Config> BitSet<Conf>

pub fn serialize(&self, w: &mut impl Write) -> Result<()>

Serialize container to a binary format.

Format

In little endian.

lvl0_mask|[lvl1_mask;..]|[data;..]

pub fn deserialize(r: &mut impl Read) -> Result<Self>

Deserialize from serialized BitSet.

impl<Conf: Config> BitSet<Conf>

pub const fn max_capacity() -> usize

Max usize, BitSet with this Config can hold.

pub fn new() -> Self

pub fn insert(&mut self, index: usize)

Panics

Panics, if index is out of index range.

pub fn insert_block(&mut self, block: DataBlock<Conf::DataBitBlock>)

Panics

Panics, if block is out of index range.

pub fn remove(&mut self, index: usize) -> bool

Returns false if index is not in bitset.

Panics

Panics, if index is out of index range.

impl<Conf> BitSet<Conf>

where Conf: Config,

pub fn block_iter<'a>(&'a self) -> BlockIter<&'a Self>

pub fn iter<'a>(&'a self) -> IndexIter<&'a Self>

pub fn contains(&self, index: usize) -> bool

pub fn is_empty(&self) -> bool

See BitSetInterface::is_empty()

Trait Implementations

impl<Conf, Rhs> BitAnd<Rhs> for &BitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: Config,

fn bitand(self, rhs: Rhs) -> Self::Output

Returns intersection of self and rhs bitsets.

type Output = Apply<And, &BitSet<Conf>, Rhs>

The resulting type after applying the & operator.

impl<Conf, Rhs> BitOr<Rhs> for &BitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: Config,

fn bitor(self, rhs: Rhs) -> Self::Output

Returns union of self and rhs bitsets.

type Output = Apply<Or, &BitSet<Conf>, Rhs>

The resulting type after applying the | operator.

impl<Conf: Config> BitSetBase for BitSet<Conf>

const TRUSTED_HIERARCHY: bool = true

Does each raised bit in hierarchy bitblock correspond to non-empty data block?

type Conf = Conf

impl<Conf> BitSetInterface for &BitSet<Conf>

where Conf: Config,

fn block_iter(&self) -> BlockIter<&Self>

fn iter(&self) -> IndexIter<&Self>

fn into_block_iter(self) -> BlockIter<Self>

fn contains(&self, index: usize) -> bool

fn is_empty(&self) -> bool

O(1) if TRUSTED_HIERARCHY, O(N) otherwise.

impl<Conf, Rhs> BitXor<Rhs> for &BitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: Config,

fn bitxor(self, rhs: Rhs) -> Self::Output

Returns symmetric difference of self and rhs bitsets.

type Output = Apply<Xor, &BitSet<Conf>, Rhs>

The resulting type after applying the ^ operator.

impl<Conf: Config> Clone for BitSet<Conf>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<Conf> Debug for BitSet<Conf>

where Conf: Config,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Conf: Config> Default for BitSet<Conf>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, Conf: Config> Deserialize<'de> for BitSet<Conf>

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<Conf: Config> Extend<DataBlock<<Conf as Config>::DataBitBlock>> for BitSet<Conf>

fn extend<T: IntoIterator<Item = DataBlock<Conf::DataBitBlock>>>( &mut self, iter: T, )

It is allowed for blocks with the same range to repeat in iterator. Like ([1,42], [15,27,61]). Their data will be merged.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<Conf: Config> Extend<usize> for BitSet<Conf>

fn extend<T: IntoIterator<Item = usize>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<Conf: Config, const N: usize> From<[usize; N]> for BitSet<Conf>

fn from(value: [usize; N]) -> Self

Converts to this type from the input type.

impl<Conf, B> From<B> for BitSet<Conf>

where Conf: Config, B: BitSetInterface<Conf = Conf>,

fn from(bitset: B) -> Self

Materialize any BitSetInterface.

impl<Conf: Config> FromIterator<DataBlock<<Conf as Config>::DataBitBlock>> for BitSet<Conf>

fn from_iter<T: IntoIterator<Item = DataBlock<Conf::DataBitBlock>>>( iter: T, ) -> Self

It is allowed for blocks with the same range to repeat in iterator. Like ([1,42], [15,27,61]). Their data will be merged.

impl<Conf: Config> FromIterator<usize> for BitSet<Conf>

fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self

Creates a value from an iterator.

impl<Conf> IntoIterator for &BitSet<Conf>

where Conf: Config,

type Item = usize

The type of the elements being iterated over.

type IntoIter = IndexIter<&BitSet<Conf>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<Conf, Rhs> PartialEq<Rhs> for BitSet<Conf>

where Rhs: LevelMasksIterExt<Conf = <Self as BitSetBase>::Conf>, Conf: Config,

fn eq(&self, other: &Rhs) -> bool

Works faster with TRUSTED_HIERARCHY.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<Conf: Config> Serialize for BitSet<Conf>

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<Conf, Rhs> Sub<Rhs> for &BitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: Config,

fn sub(self, rhs: Rhs) -> Self::Output

Returns difference of self and rhs bitsets.

Or relative complement of rhs in self.

type Output = Apply<Sub, &BitSet<Conf>, Rhs>

The resulting type after applying the - operator.

impl<Conf> Eq for BitSet<Conf>

where Conf: Config,