Struct hi_sparse_bitset::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 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 lowest algorithmic complexity.) Insert/remove/contains is fast O(1) too.

Implementations

impl<Conf> BitSet<Conf>

where Conf: Config,

pub fn new() -> Self

pub const fn max_capacity() -> usize

Max usize, bitset with this Conf can hold.

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

Safety

Will panic, if index is out of range.

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

Returns false if index is invalid/not in bitset.

pub unsafe fn remove_unchecked(&mut self, index: usize)

Safety

index MUST exists in HiSparseBitset!

impl<Conf> BitSet<Conf>

where Conf: Config,

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

pub fn iter<'a>(&'a self) -> CachingIndexIter<&'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>

type Conf = Conf

const TRUSTED_HIERARCHY: bool = true

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

impl<Conf> BitSetInterface for &BitSet<Conf>

where Conf: Config,

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

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

fn into_block_iter(self) -> CachingBlockIter<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> Clone for BitSet<Conf>

where Conf: Config,

fn clone(&self) -> Self

Returns a copy 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> Default for BitSet<Conf>

where Conf: Config,

fn default() -> Self

Returns the “default value” for a type.

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

where Conf: Config,

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

Converts to this type from the input type.

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

where Conf: Config,

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 = CachingIndexIter<&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> LevelMasks for BitSet<Conf>

where Conf: Config,

fn level0_mask(&self) -> <Self::Conf as Config>::Level0BitBlock

unsafe fn level1_mask( &self, level0_index: usize ) -> <Self::Conf as Config>::Level1BitBlock

Safety

unsafe fn data_mask( &self, level0_index: usize, level1_index: usize ) -> <Self::Conf as Config>::DataBitBlock

Safety

impl<Conf> LevelMasksIterExt for BitSet<Conf>

where Conf: Config,

type IterState = <RawBitSet<Conf, Block<<Conf as Config>::Level0BitBlock, <Conf as Config>::Level0BlockIndices>, Block<<Conf as Config>::Level1BitBlock, <Conf as Config>::Level1BlockIndices>, Block<<Conf as Config>::DataBitBlock, [usize; 0]>> as LevelMasksIterExt>::IterState

Consists from child states (if any) + Self state.

type Level1BlockData = <RawBitSet<Conf, Block<<Conf as Config>::Level0BitBlock, <Conf as Config>::Level0BlockIndices>, Block<<Conf as Config>::Level1BitBlock, <Conf as Config>::Level1BlockIndices>, Block<<Conf as Config>::DataBitBlock, [usize; 0]>> as LevelMasksIterExt>::Level1BlockData

Level1 block related data, used to speed up data_mask access.

fn make_iter_state(&self) -> Self::IterState

unsafe fn drop_iter_state(&self, state: &mut ManuallyDrop<Self::IterState>)

Having separate function for drop not strictly necessary, since IterState can actually drop itself. But! This allows not to store cache size within IterState. Which makes FixedCache CacheData ZST, if its childs are ZSTs, and which makes cache construction and destruction noop. Which is important for short iteration sessions.

unsafe fn init_level1_block_data( &self, state: &mut Self::IterState, level1_block_data: &mut MaybeUninit<Self::Level1BlockData>, level0_index: usize ) -> (<Self::Conf as Config>::Level1BitBlock, bool)

Init level1_block_data and return (Level1Mask, is_not_empty).

unsafe fn data_mask_from_block_data( level1_block_data: &Self::Level1BlockData, level1_index: usize ) -> <Self::Conf as Config>::DataBitBlock

Safety

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

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

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,