extramojo
collections
bitvec
BitVec

BitVec

Mojo struct 🡭

BitVec

@memory_only
struct BitVec

A growable bitfield.

This uses one bit per bool for storage.

The bits are stored in Self.WORD_DTYPE words. This is optimized for compactness and speed.

Aliases

  • WORD_DTYPE = uint64 if (is_gpu() ^ True) else uint32
  • WORD_BYTEWIDTH = (div_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8) + -1) if ((uint64 if (is_gpu() ^ True) else uint32.bitwidth() < 0) & ((rem_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8) == 0) ^ True)) else div_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8)
  • WORD = SIMD[uint64 if (is_gpu() ^ True) else uint32, 1]

Fields

  • data (UnsafePointer[SIMD[uint64 if (is_gpu() ^ True) else uint32, 1], alignment=(div_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8) + -1) if ((uint64 if (is_gpu() ^ True) else uint32.bitwidth() < 0) & ((rem_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8) == 0) ^ True)) else div_s(#lit.struct.extract<:@stdlib::@builtin::@int::@Int apply(:!lit.generator<("self": !lit.struct<@stdlib::@builtin::@dtype::@DType>) -> !lit.struct<@stdlib::@builtin::@int::@Int>> @stdlib::@builtin::@dtype::@DType::@"bitwidth(::DType)", cond(not(#lit.struct.extract<:@stdlib::@builtin::@bool::@Bool apply(:!lit.generator<() -> !lit.struct<@stdlib::@builtin::@bool::@Bool>> @stdlib::@sys::@info::@"is_gpu()"), "value">), {:dtype ui64}, {:dtype ui32})), "value">, 8)]): The data storage.

Implemented traits

AnyType, Boolable, Copyable, ExplicitlyCopyable, Movable, Sized, UnknownDestructibility, Writable

Methods

➕  ➖

__init__ 

fn __init__(out self)

Details Args:

  • self (Self)

Returns:

Self

fn __init__(out self, *, capacity: UInt)

Capacity measured in bits. Args:

  • capacity (UInt)
  • self (Self)

Returns:

Self

fn __init__(out self, *, length: UInt, fill: Bool = False)

Create a new bitvec with a known length and fill. Args:

  • length (UInt): Known length in bits.
  • fill (Bool): The value to fill the bitvec with.
  • self (Self)

Returns:

Self

fn __init__(out self, var *values: Bool, *, __list_literal__: Tuple[] = Tuple())

Constructs a BitVec from the given values. Args:

  • *values (Bool): The values to populate the BitVec with.
  • list_literal (Tuple): Tell Mojo to use this method for list literals.
  • self (Self)

Returns:

Self

fn __init__(out self, *, var elements: VariadicListMem[Bool, origin, is_owned])

Constructs a BitVec from the given values. Args:

  • elements (VariadicListMem): The values to populate the list with.
  • self (Self)

Returns:

Self

__moveinit__ 

@staticmethod
fn __moveinit__(out self, var other: Self)

Details Args:

  • other (Self)
  • self (Self)

Returns:

Self

__del__ 

fn __del__(var self)

Details Args:

  • self (Self)

__bool__ 

fn __bool__(self) -> Bool

Checks if the BitVec is non-empty (contains at least one value). Equivalent to len(self) != 0 or not self.is_empty().

Args:

  • self (Self)

Returns:

Bool: True if at least one value is in BitVec., False otherwise.

__getitem__ 

fn __getitem__(self, idx: UInt) -> Bool

Get the bit at the given index. Args:

  • self (Self)
  • idx (UInt): The index of the bit.

Returns:

Bool

__setitem__ 

fn __setitem__(mut self, idx: UInt, value: Bool)

Set the bit at the given index. Args:

  • self (Self)
  • idx (UInt): The index of the bit to set.
  • value (Bool): The value to set the bit to.

__eq__ 

fn __eq__(self, other: Self) -> Bool

Check the equality of self and other. Args:

  • self (Self)
  • other (Self): The BitVec to compare against.

Returns:

Bool: True if equal, False otherwise.

__ne__ 

fn __ne__(self, other: Self) -> Bool

Check the equality of self and other. Args:

  • self (Self)
  • other (Self): The BitVec to compare against.

Returns:

Bool: True if not equal, False otherwise.

__sub__ 

fn __sub__(self, other: Self) -> Self

Returns a new BitVec that is the difference of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-: 0 0 0 1 1 1 1 0

Args:

  • self (Self)
  • other (Self): The BitVec to subtract from self.

Returns:

Self: A new BitVec containing elements from self that are not in other.

__and__ 

fn __and__(self, other: Self) -> Self

Returns a new BitVec that is the intersection of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&: 0 0 1 0 0 0 0 0

Args:

  • self (Self)
  • other (Self): The BitVec to intersect with.

Returns:

Self: A new BitVec containing only the elements present in both sets.

__or__ 

fn __or__(self, other: Self) -> Self

Returns a new BitVec that is the union of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|: 1 1 1 1 1 1 1 0

Args:

  • self (Self)
  • other (Self): The BitVec to union with.

Returns:

Self: A new BitVec containing all elements from both sets.

__isub__ 

fn __isub__(mut self, other: Self)

Modifies self to be the difference of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-= 0 0 0 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to subtract from self.

__iand__ 

fn __iand__(mut self, other: Self)

Modifies self to be the intersection of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&= 0 0 1 0 0 0 0 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to intersect with.

__ior__ 

fn __ior__(mut self, other: Self)

Modifies self to be the union of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|= 1 1 1 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to union with.

copy 

fn copy(self) -> Self

Details Args:

  • self (Self)

Returns:

Self

__len__ 

fn __len__(self) -> Int

The number of bits in the bitvec. Args:

  • self (Self)

Returns:

Int

capacity 

fn capacity(self) -> UInt

Returns the capacity in bits. Args:

  • self (Self)

Returns:

UInt

word_len 

fn word_len(self) -> UInt

Get the number of words that have been set. Args:

  • self (Self)

Returns:

UInt

is_empty 

fn is_empty(self) -> Bool

Checks if the BitVec has any values stored in it. Equivalent to len(self) == 0. Note that this checks the logical size, not the allocated capacity.

Args:

  • self (Self)

Returns:

Bool: True if no values are stored in the BitVec.

resize 

fn resize(mut self, new_size: UInt, fill: Bool)

Resize the bitvec, filling any new size with fill. Args:

  • self (Self)
  • new_size (UInt): The new size in bits.
  • fill (Bool): The value to use to populate new elements.

shrink 

fn shrink(mut self, new_size: UInt)

Resizes to the given new size (in bits) which must be <= the current size. Notes: With no new value provided, the new size must be smaller than or equal to the current one. Elements at the end are discarded.

Args:

  • self (Self)
  • new_size (UInt): The new size in bits.

reserve 

fn reserve(mut self, new_capacity: UInt)

Reserves the requested capacity (in bits). Notes: If the current capacity is greater or equal, this is a no-op. Otherwise, the storage is reallocated and the data is moved.

Args:

  • self (Self)
  • new_capacity (UInt): The new capacity, in bits.

test 

fn test(self, idx: UInt) -> Bool

Tests if the bit at the specified index idx is set (is 1). Aborts if idx is negative or greater than or equal to the compile-time size.

Args:

  • self (Self)
  • idx (UInt): The non-negative index of the bit to test (must be < size).

Returns:

Bool: True if the bit at idx is set, False otherwise.

clear 

fn clear(mut self)

Clear the BitVec. This sets the length to 0.

Args:

  • self (Self)
fn clear(mut self, idx: UInt)

Clear the bit at the given index (set to 0). Args:

  • self (Self)
  • idx (UInt): The index of the bit to clear.

zero_all 

fn zero_all(mut self)

Set all bits to zero. Args:

  • self (Self)

set_and_check 

fn set_and_check(mut self, idx: UInt) -> Bool

Set the bit at the given index. If the value was already set, return False, otherwise True. Args:

  • self (Self)
  • idx (UInt): The index of the bit to set.

Returns:

Bool: False if the bit was already set, True if it was not.

set 

fn set(mut self, idx: UInt)

Set the bit at the given index to 1. Args:

  • self (Self)
  • idx (UInt): The index of the bit to set.

clear_and_check 

fn clear_and_check(mut self, idx: UInt) -> Bool

Clear the bit at the given index. If the value was already clear (0, False), return False, otherwise True. Args:

  • self (Self)
  • idx (UInt): The index of the bit to clear.

Returns:

Bool: False if the bit was already clear, True if it was not.

toggle 

fn toggle(mut self, idx: UInt)

Toggles (inverts) the bit at the specified index idx. Args:

  • self (Self)
  • idx (UInt): The non-negative index of the bit to toggle (must be < len(BitVec)).

append 

fn append(mut self, value: Bool)

Append an item to the end of the BitVec. Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

  • self (Self)
  • value (Bool): The value to append.

append_true 

fn append_true(mut self)

Append a set bit to the end of the BitVec. Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

  • self (Self)

append_false 

fn append_false(mut self)

Append a cleared bit to the end of the BitVec. Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

  • self (Self)

pop_back 

fn pop_back(mut self) -> Bool

Remove and return the last item in the BitVec. Args:

  • self (Self)

Returns:

Bool

count_set_bits 

fn count_set_bits(self) -> UInt

Count the total number of set bits. Args:

  • self (Self)

Returns:

UInt

rank 

fn rank(self, bit_idx: UInt) -> UInt

Count the total number of set bits up to (but not including) bit_idx. TODO: implement another struct that builds a rank/select index.

References:

Args:

  • self (Self)
  • bit_idx (UInt): Index to get the rank for.

Returns:

UInt

count_clear_bits 

fn count_clear_bits(self) -> UInt

Count the total number of clear bits. Args:

  • self (Self)

Returns:

UInt

union 

fn union(self, other: Self) -> Self

Returns a new BitVec that is the union of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|: 1 1 1 1 1 1 1 0

Args:

  • self (Self)
  • other (Self): The BitVec to union with.

Returns:

Self: A new BitVec containing all elements from both sets.

intersection 

fn intersection(self, other: Self) -> Self

Returns a new BitVec that is the intersection of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&: 0 0 1 0 0 0 0 0

Args:

  • self (Self)
  • other (Self): The BitVec to intersect with.

Returns:

Self: A new BitVec containing only the elements present in both sets.

difference 

fn difference(self, other: Self) -> Self

Returns a new BitVec that is the difference of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-: 0 0 0 1 1 1 1 0

Args:

  • self (Self)
  • other (Self): The BitVec to subtract from self.

Returns:

Self: A new BitVec containing elements from self that are not in other.

union_update 

fn union_update(mut self, other: Self)

Modifies self to be the union of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|= 1 1 1 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to union with.

intersection_update 

fn intersection_update(mut self, other: Self)

Modifies self to be the intersection of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&= 0 0 1 0 0 0 0 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to intersect with.

difference_update 

fn difference_update(mut self, other: Self)

Modifies self to be the difference of self and other. 

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-= 0 0 0 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

  • self (Self)
  • other (Self): The BitVec to subtract from self.

write_to 

fn write_to[W: Writer](self, mut writer: W)

Write the bitvec in a nice format. Parameters:

  • W (Writer)

Args:

  • self (Self)
  • writer (W)