Struct SparseMap

Source

pub struct SparseMap { /* private fields */ }

Expand description

A sparse, compressed, run-length-encoded bitset over u64 indices.

See the crate-level documentation for the data model.

Implementations§

Source §

impl SparseMap

Source

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

Returns an iterator over the set bits, in ascending order.

use sparsemap::SparseMap;
let m: SparseMap = [3, 1, 4, 1, 5].into_iter().collect();
assert_eq!(m.iter().collect::<Vec<_>>(), vec![1, 3, 4, 5]);

Source

pub fn to_vec(&self) -> Vec<u64>

Collects the set bits into a Vec<u64>, ascending.

Allocates; provided for parity with the C sm_to_array.

Source §

impl SparseMap

Source

pub fn union(&self, other: &SparseMap) -> SparseMap

Returns the union (self ∪ other): bits set in either map.

Source

pub fn intersection(&self, other: &SparseMap) -> SparseMap

Returns the intersection (self ∩ other): bits set in both maps.

Source

pub fn difference(&self, other: &SparseMap) -> SparseMap

Returns the difference (self \ other): bits set in self but not in other.

Source

pub fn symmetric_difference(&self, other: &SparseMap) -> SparseMap

Returns the symmetric difference (self △ other): bits set in exactly one map.

Source

pub fn intersects(&self, other: &SparseMap) -> bool

Returns true if self and other share at least one bit.

Source

pub fn is_subset(&self, other: &SparseMap) -> bool

Returns true if every bit set in self is also set in other.

Source

pub fn is_superset(&self, other: &SparseMap) -> bool

Returns true if every bit set in other is also set in self.

Source

pub fn shifted(&self, offset: i64) -> SparseMap

Returns a copy with every bit shifted by offset (positive = toward higher indices). Bits that would move below zero or above u64::MAX are dropped, matching the C sm_offset.

Source §

impl SparseMap

Source

pub fn to_bytes(&self) -> Vec<u8> ⓘ

Serializes the map into the C-compatible wire format (version 2: 8-byte chunk-start offsets, addressing the full 64-bit universe).

Source

pub fn from_bytes(buf: &[u8]) -> Result<SparseMap, DecodeError>

Deserializes a buffer produced by SparseMap::to_bytes or by the C sm_serialize.

§Errors

Returns a DecodeError for any malformed input rather than panicking; arbitrary bytes are safe to feed in.

Source §

impl SparseMap

Source

pub const fn new() -> Self

Creates an empty map.

Source

pub fn is_empty(&self) -> bool

Returns true if the map contains no set bits.

Source

pub fn clear(&mut self)

Removes all bits, retaining no allocation.

Source

pub fn cardinality(&self) -> u64

Returns the number of set bits (the cardinality).

Runs are counted in O(1), so this is cheap even for maps dominated by long runs.

Source

pub fn len(&self) -> u64

Returns the number of set bits.

An alias for cardinality, named to match the Rust collection convention (and roaring::RoaringBitmap), so the type drops in for code written against those APIs.

Source

pub fn contains(&self, idx: u64) -> bool

Returns true if bit idx is set.

Source

pub fn insert(&mut self, idx: u64) -> bool

Sets bit idx. Returns true if the bit was newly set, false if it was already set (mirroring alloc::collections::BTreeSet::insert).

Source

pub fn remove(&mut self, idx: u64) -> bool

Clears bit idx. Returns true if the bit had been set.

Source

pub fn min(&self) -> Option<u64>

Returns the smallest set bit, or None if the map is empty.

Source

pub fn max(&self) -> Option<u64>

Returns the largest set bit, or None if the map is empty.

Source

pub fn rank(&self, idx: u64) -> u64

Returns the number of set bits strictly less than idx (the standard succinct-structure rank).

rank(0) is always 0; rank(u64::MAX) + contains(u64::MAX) as u64 is the cardinality.

Source

pub fn select(&self, n: u64) -> Option<u64>

Returns the position of the n-th set bit (0-based), or None if there are n or fewer set bits.

select(0) is min.

Source

pub fn insert_range(&mut self, start: u64, end: u64)

Sets every bit in the half-open range [start, end).

Source

pub fn remove_range(&mut self, start: u64, end: u64)

Clears every bit in the half-open range [start, end).

Source

pub fn span(&self, start: u64, len: u64, value: bool) -> Option<u64>

Returns the start of the first run of at least len consecutive bits all equal to value, beginning the search at start, or None if there is no such run.