Struct MutableBitmap

pub struct MutableBitmap { /* private fields */ }

A container of booleans. MutableBitmap is semantically equivalent to Vec<bool>.

The two main differences against Vec<bool> is that each element stored as a single bit, thereby:

• it uses 8x less memory
• it cannot be represented as &[bool] (i.e. no pointer arithmetics).

A MutableBitmap can be converted to a Bitmap at O(1).

Examples

use polars_arrow::bitmap::MutableBitmap;

let bitmap = MutableBitmap::from([true, false, true]);
assert_eq!(bitmap.iter().collect::<Vec<_>>(), vec![true, false, true]);

// creation directly from bytes
let mut bitmap = MutableBitmap::try_new(vec![0b00001101], 5).unwrap();
// note: the first bit is the left-most of the first byte
assert_eq!(bitmap.iter().collect::<Vec<_>>(), vec![true, false, true, true, false]);
// we can also get the slice:
assert_eq!(bitmap.as_slice(), [0b00001101u8].as_ref());
// debug helps :)
assert_eq!(format!("{:?}", bitmap), "Bitmap { len: 5, offset: 0, bytes: [0b___01101] }");

// It supports mutation in place
bitmap.set(0, false);
assert_eq!(format!("{:?}", bitmap), "Bitmap { len: 5, offset: 0, bytes: [0b___01100] }");
// and `O(1)` random access
assert_eq!(bitmap.get(0), false);

Implementation

This container is internally a Vec<u8>.

Implementations

impl MutableBitmap

pub fn new() -> Self

Initializes an empty MutableBitmap.

pub fn try_new(bytes: Vec<u8>, length: usize) -> PolarsResult<Self>

Initializes a new MutableBitmap from a Vec<u8> and a length.

Errors

This function errors iff length > bytes.len() * 8

pub fn from_vec(buffer: Vec<u8>, length: usize) -> Self

Initializes a MutableBitmap from a Vec<u8> and a length. This function is O(1).

Panic

Panics iff the length is larger than the length of the buffer times 8.

pub fn with_capacity(capacity: usize) -> Self

Initializes a pre-allocated MutableBitmap with capacity for capacity bits.

pub fn push(&mut self, value: bool)

Pushes a new bit to the MutableBitmap, re-sizing it if necessary.

pub fn pop(&mut self) -> Option<bool>

Pop the last bit from the MutableBitmap. Note if the MutableBitmap is empty, this method will return None.

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

Returns whether the position index is set.

Panics

Panics iff index >= self.len().

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

Returns whether the position index is set.

Safety

The caller must ensure index < self.len().

pub fn set(&mut self, index: usize, value: bool)

Sets the position index to value

Panics

Panics iff index >= self.len().

pub unsafe fn or_pos_unchecked(&mut self, index: usize, value: bool)

Sets the position index to the OR of its original value and value.

Safety

It’s undefined behavior if index >= self.len().

pub unsafe fn and_pos_unchecked(&mut self, index: usize, value: bool)

Sets the position index to the AND of its original value and value.

Safety

It’s undefined behavior if index >= self.len().

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

constructs a new iterator over the bits of MutableBitmap.

pub fn clear(&mut self)

Empties the MutableBitmap.

pub fn extend_constant(&mut self, additional: usize, value: bool)

Extends MutableBitmap by additional values of constant value.

Implementation

This function is an order of magnitude faster than pushing element by element.

pub fn resize(&mut self, length: usize, value: bool)

Resizes the MutableBitmap to the specified length, inserting value if the length is bigger than the current length.

pub fn from_len_zeroed(length: usize) -> Self

Initializes a zeroed MutableBitmap.

pub fn from_len_set(length: usize) -> Self

Initializes a MutableBitmap with all values set to valid/ true.

pub fn reserve(&mut self, additional: usize)

Reserves additional bits in the MutableBitmap, potentially re-allocating its buffer.

pub fn capacity(&self) -> usize

Returns the capacity of MutableBitmap in number of bits.

pub unsafe fn push_unchecked(&mut self, value: bool)

Pushes a new bit to the MutableBitmap

Safety

The caller must ensure that the MutableBitmap has sufficient capacity.

pub fn unset_bits(&self) -> usize

Returns the number of unset bits on this MutableBitmap.

Guaranteed to be <= self.len().

Implementation

This function is O(N)

pub fn set_bits(&self) -> usize

Returns the number of set bits on this MutableBitmap.

Guaranteed to be <= self.len().

Implementation

This function is O(N)

pub fn len(&self) -> usize

Returns the length of the MutableBitmap.

pub fn is_empty(&self) -> bool

Returns whether MutableBitmap is empty.

pub unsafe fn set_unchecked(&mut self, index: usize, value: bool)

Sets the position index to value

Safety

Caller must ensure that index < self.len()

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the MutableBitmap to fit its current length.

pub fn chunks<T: BitChunk>(&self) -> BitChunks<'_, T>

Returns an iterator over bits in bit chunks BitChunk.

This iterator is useful to operate over multiple bits via e.g. bitwise.

pub fn intersects_with(&self, other: &Self) -> bool

pub fn freeze(self) -> Bitmap

impl MutableBitmap

pub fn extend_from_trusted_len_iter<I: TrustedLen<Item = bool>>( &mut self, iterator: I, )

Extends self from a TrustedLen iterator.

pub unsafe fn extend_from_trusted_len_iter_unchecked<I: Iterator<Item = bool>>( &mut self, iterator: I, )

Extends self from an iterator of trusted len.

Safety

The caller must guarantee that the iterator has a trusted len.

pub unsafe fn from_trusted_len_iter_unchecked<I>(iterator: I) -> Self

where I: Iterator<Item = bool>,

Creates a new MutableBitmap from an iterator of booleans.

Safety

The iterator must report an accurate length.

pub fn from_trusted_len_iter<I>(iterator: I) -> Self

where I: TrustedLen<Item = bool>,

Creates a new MutableBitmap from an iterator of booleans.

pub fn try_from_trusted_len_iter<E, I>(iterator: I) -> Result<Self, E>

where I: TrustedLen<Item = Result<bool, E>>,

Creates a new MutableBitmap from an iterator of booleans.

pub unsafe fn try_from_trusted_len_iter_unchecked<E, I>( iterator: I, ) -> Result<Self, E>

where I: Iterator<Item = Result<bool, E>>,

Creates a new MutableBitmap from an falible iterator of booleans.

Safety

The caller must guarantee that the iterator is TrustedLen.

pub unsafe fn extend_from_slice_unchecked( &mut self, slice: &[u8], offset: usize, length: usize, )

Extends the MutableBitmap from a slice of bytes with optional offset. This is the fastest way to extend a MutableBitmap.

Implementation

When both MutableBitmap’s length and offset are both multiples of 8, this function performs a memcopy. Else, it first aligns bit by bit and then performs a memcopy.

Safety

Caller must ensure offset + length <= slice.len() * 8

pub fn extend_from_slice(&mut self, slice: &[u8], offset: usize, length: usize)

Extends the MutableBitmap from a slice of bytes with optional offset. This is the fastest way to extend a MutableBitmap.

Implementation

When both MutableBitmap’s length and offset are both multiples of 8, this function performs a memcopy. Else, it first aligns bit by bit and then performs a memcopy.

pub fn extend_from_bitmap(&mut self, bitmap: &Bitmap)

Extends the MutableBitmap from a Bitmap.

pub fn as_slice(&self) -> &[u8]

Returns the slice of bytes of this MutableBitmap. Note that the last byte may not be fully used.

pub fn as_mut_slice(&mut self) -> &mut [u8]

Returns the slice of bytes of this MutableBitmap. Note that the last byte may not be fully used.

Trait Implementations

impl<'a> BitAnd<&'a Bitmap> for MutableBitmap

type Output = MutableBitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: &'a Bitmap) -> Self

Performs the & operation.

impl<'a> BitAndAssign<&'a Bitmap> for &mut MutableBitmap

fn bitand_assign(&mut self, rhs: &'a Bitmap)

Performs the &= operation.

impl<'a> BitOr<&'a Bitmap> for MutableBitmap

type Output = MutableBitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: &'a Bitmap) -> Self

Performs the | operation.

impl<'a> BitOrAssign<&'a Bitmap> for &mut MutableBitmap

fn bitor_assign(&mut self, rhs: &'a Bitmap)

Performs the |= operation.

impl<'a> BitOrAssign<&'a MutableBitmap> for &mut MutableBitmap

fn bitor_assign(&mut self, rhs: &'a MutableBitmap)

Performs the |= operation.

impl<'a> BitXor<&'a Bitmap> for MutableBitmap

type Output = MutableBitmap

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &'a Bitmap) -> Self

Performs the ^ operation.

impl<'a> BitXorAssign<&'a Bitmap> for &mut MutableBitmap

fn bitxor_assign(&mut self, rhs: &'a Bitmap)

Performs the ^= operation.

impl Clone for MutableBitmap

fn clone(&self) -> MutableBitmap

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for MutableBitmap

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

Formats the value using the given formatter.

impl Default for MutableBitmap

fn default() -> Self

Returns the “default value” for a type.

impl From<MutableBitmap> for Bitmap

fn from(buffer: MutableBitmap) -> Self

Converts to this type from the input type.

impl From<MutableBitmap> for Option<Bitmap>

fn from(buffer: MutableBitmap) -> Self

Converts to this type from the input type.

impl<P: AsRef<[bool]>> From<P> for MutableBitmap

fn from(slice: P) -> Self

Converts to this type from the input type.

impl FromIterator<bool> for MutableBitmap

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = bool>,

Creates a value from an iterator.

impl<'a> IntoIterator for &'a MutableBitmap

type Item = bool

The type of the elements being iterated over.

type IntoIter = BitmapIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl Not for MutableBitmap

type Output = MutableBitmap

The resulting type after applying the ! operator.

fn not(self) -> Self

Performs the unary ! operation.

impl PartialEq for MutableBitmap

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

Tests for self and other values to be equal, and is used by ==.

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 Pushable<bool> for MutableBitmap

type Freeze = Bitmap

fn reserve(&mut self, additional: usize)

fn len(&self) -> usize

fn push(&mut self, value: bool)

fn push_null(&mut self)

fn extend_constant(&mut self, additional: usize, value: bool)

fn extend_null_constant(&mut self, additional: usize)

fn freeze(self) -> Self::Freeze

fn with_capacity(capacity: usize) -> Self

fn extend_n(&mut self, n: usize, iter: impl Iterator<Item = T>)