Struct Bitmap

pub struct Bitmap { /* private fields */ }

An immutable container semantically equivalent to Arc<Vec<bool>> but represented as Arc<Vec<u8>> where each boolean is represented as a single bit.

Examples

use polars_arrow::bitmap::{Bitmap, MutableBitmap};

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

// creation directly from bytes
let bitmap = Bitmap::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(), 0, 5));
// debug helps :)
assert_eq!(format!("{:?}", bitmap), "Bitmap { len: 5, offset: 0, bytes: [0b___01101] }");

// it supports copy-on-write semantics (to a `MutableBitmap`)
let bitmap: MutableBitmap = bitmap.into_mut().right().unwrap();
assert_eq!(bitmap, MutableBitmap::from([true, false, true, true, false]));

// slicing is 'O(1)' (data is shared)
let bitmap = Bitmap::try_new(vec![0b00001101], 5).unwrap();
let mut sliced = bitmap.clone();
sliced.slice(1, 4);
assert_eq!(sliced.as_slice(), ([0b00001101u8].as_ref(), 1, 4)); // 1 here is the offset:
assert_eq!(format!("{:?}", sliced), "Bitmap { len: 4, offset: 1, bytes: [0b___0110_] }");
// when sliced (or cloned), it is no longer possible to `into_mut`.
let same: Bitmap = sliced.into_mut().left().unwrap();

Implementations

impl Bitmap

pub fn new() -> Self

Initializes an empty Bitmap.

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

Initializes a new Bitmap from vector of bytes and a length.

Errors

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

pub fn len(&self) -> usize

Returns the length of the Bitmap.

pub fn is_empty(&self) -> bool

Returns whether Bitmap is empty

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

Returns a new iterator of bool over this bitmap

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 fast_iter_u32(&self) -> FastU32BitmapIter<'_>

Returns a fast iterator that gives 32 bits at a time. Has a remainder that must be handled separately.

pub fn fast_iter_u56(&self) -> FastU56BitmapIter<'_>

Returns a fast iterator that gives 56 bits at a time. Has a remainder that must be handled separately.

pub fn fast_iter_u64(&self) -> FastU64BitmapIter<'_>

Returns a fast iterator that gives 64 bits at a time. Has a remainder that must be handled separately.

pub fn true_idx_iter(&self) -> TrueIdxIter<'_>

Returns an iterator that only iterates over the set bits.

pub fn aligned<T: BitChunk>(&self) -> AlignedBitmapSlice<'_, T>

Returns the bits of this Bitmap as a AlignedBitmapSlice.

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

Returns the byte slice of this Bitmap.

The returned tuple contains:

• .1: The byte slice, truncated to the start of the first bit. So the start of the slice is within the first 8 bits.
• .2: The start offset in bits on a range 0 <= offsets < 8.
• .3: The length in number of bits.

pub fn set_bits(&self) -> usize

Returns the number of set bits on this Bitmap.

See unset_bits for details.

pub fn lazy_set_bits(&self) -> Option<usize>

Returns the number of set bits on this Bitmap if it is known.

See lazy_unset_bits for details.

pub fn unset_bits(&self) -> usize

Returns the number of unset bits on this Bitmap.

Guaranteed to be <= self.len().

Implementation

This function counts the number of unset bits if it is not already computed. Repeated calls use the cached bitcount.

pub fn lazy_unset_bits(&self) -> Option<usize>

Returns the number of unset bits on this Bitmap if it is known.

Guaranteed to be <= self.len().

pub unsafe fn update_bit_count(&mut self, bits_set: usize)

Updates the count of the number of set bits on this Bitmap.

Safety

The number of set bits must be correct.

pub fn slice(&mut self, offset: usize, length: usize)

Slices self, offsetting by offset and truncating up to length bits.

Panic

Panics iff offset + length > self.length, i.e. if the offset and length exceeds the allocated capacity of self.

pub unsafe fn slice_unchecked(&mut self, offset: usize, length: usize)

Slices self, offsetting by offset and truncating up to length bits.

Safety

The caller must ensure that self.offset + offset + length <= self.len()

pub fn sliced(self, offset: usize, length: usize) -> Self

Slices self, offsetting by offset and truncating up to length bits.

Panic

Panics iff offset + length > self.length, i.e. if the offset and length exceeds the allocated capacity of self.

pub unsafe fn sliced_unchecked(self, offset: usize, length: usize) -> Self

Slices self, offsetting by offset and truncating up to length bits.

Safety

The caller must ensure that self.offset + offset + length <= self.len()

pub fn get_bit(&self, i: usize) -> bool

Returns whether the bit at position i is set.

Panics

Panics iff i >= self.len().

pub unsafe fn get_bit_unchecked(&self, i: usize) -> bool

Unsafely returns whether the bit at position i is set.

Safety

Unsound iff i >= self.len().

pub fn into_mut(self) -> Either<Self, MutableBitmap>

Converts this Bitmap to MutableBitmap, returning itself if the conversion is not possible

This operation returns a MutableBitmap iff:

• this Bitmap is not an offsetted slice of another Bitmap
• this Bitmap has not been cloned (i.e. [Arc]::get_mut yields Some)
• this Bitmap was not imported from the c data interface (FFI)

pub fn make_mut(self) -> MutableBitmap

Converts this Bitmap into a MutableBitmap, cloning its internal buffer if required (clone-on-write).

pub fn new_zeroed(length: usize) -> Self

Initializes an new Bitmap filled with unset values.

pub fn new_with_value(value: bool, length: usize) -> Self

Initializes an new Bitmap filled with the given value.

pub fn null_count_range(&self, offset: usize, length: usize) -> usize

Counts the nulls (unset bits) starting from offset bits and for length bits.

pub fn from_u8_slice<T: AsRef<[u8]>>(slice: T, length: usize) -> Self

Creates a new Bitmap from a slice and length.

Panic

Panics iff length <= bytes.len() * 8

pub fn from_u8_vec(vec: Vec<u8>, length: usize) -> Self

Alias for Bitmap::try_new().unwrap() This function is O(1)

Panic

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

pub fn get(&self, i: usize) -> Option<bool>

Returns whether the bit at position i is set.

pub unsafe fn from_inner_unchecked( storage: SharedStorage<u8>, offset: usize, length: usize, unset_bits: Option<usize>, ) -> Self

Creates a [Bitmap] from its internal representation. This is the inverted from [Bitmap::into_inner]

Safety

Callers must ensure all invariants of this struct are upheld.

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

Checks whether two Bitmaps have shared set bits.

This is an optimized version of (self & other) != 0000...

pub fn num_intersections_with(&self, other: &Self) -> usize

Calculates the number of shared set bits between two Bitmaps.

pub fn select(&self, truthy: &Self, falsy: &Self) -> Self

Select between truthy and falsy based on self.

This essentially performs:

out[i] = if self[i] { truthy[i] } else { falsy[i] }

pub fn select_constant(&self, truthy: &Self, falsy: bool) -> Self

Select between truthy and constant falsy based on self.

This essentially performs:

out[i] = if self[i] { truthy[i] } else { falsy }

pub fn num_edges(&self) -> usize

Calculates the number of edges from 0 -> 1 and 1 -> 0.

impl Bitmap

pub unsafe fn from_trusted_len_iter_unchecked<I: Iterator<Item = bool>>( iterator: I, ) -> Self

Creates a new Bitmap from an iterator of booleans.

Safety

The iterator must report an accurate length.

pub fn from_trusted_len_iter<I: TrustedLen<Item = bool>>(iterator: I) -> Self

Creates a new Bitmap from an iterator of booleans.

pub fn try_from_trusted_len_iter<E, I: TrustedLen<Item = Result<bool, E>>>( iterator: I, ) -> Result<Self, E>

Creates a new Bitmap from a fallible iterator of booleans.

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

Creates a new Bitmap from a fallible iterator of booleans.

Safety

The iterator must report an accurate length.

Trait Implementations

impl<'b> BitAnd<&'b Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

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

Performs the & operation.

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<'b> BitOr<&'b Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: &'b Bitmap) -> 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<'b> BitXor<&'b Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the ^ operator.

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

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 Bitmap

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Bitmap

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

Formats the value using the given formatter.

impl Default for Bitmap

fn default() -> Self

Returns the “default value” for a type.

impl From<Bitmap> for BooleanArray

fn from(values: Bitmap) -> Self

Converts to this type from the input type.

impl From<MutableBitmap> for Bitmap

fn from(buffer: MutableBitmap) -> Self

Converts to this type from the input type.

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

fn from(slice: P) -> Self

Converts to this type from the input type.

impl FromData<Bitmap> for BooleanArray

fn from_data_default(values: Bitmap, validity: Option<Bitmap>) -> BooleanArray

impl FromIterator<bool> for Bitmap

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

where I: IntoIterator<Item = bool>,

Creates a value from an iterator.

impl FromTrustedLenIterator<bool> for Bitmap

fn from_iter_trusted_length<T: IntoIterator<Item = bool>>(iter: T) -> Self

where T::IntoIter: TrustedLen,

impl<'a> IntoIterator for &'a Bitmap

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 IntoIterator for Bitmap

type Item = bool

The type of the elements being iterated over.

type IntoIter = IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl Not for &Bitmap

type Output = Bitmap

The resulting type after applying the ! operator.

fn not(self) -> Bitmap

Performs the unary ! operation.

impl PartialEq for Bitmap

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 Splitable for Bitmap

fn check_bound(&self, offset: usize) -> bool

unsafe fn _split_at_unchecked(&self, offset: usize) -> (Self, Self)

Internal implementation of split_at_unchecked. For any usage, prefer the using split_at or split_at_unchecked.

fn split_at(&self, offset: usize) -> (Self, Self)

Split Self at offset where offset <= self.len().

unsafe fn split_at_unchecked(&self, offset: usize) -> (Self, Self)

Split Self at offset without checking offset <= self.len().