BitSet

Module std.collections

import std.collections;

Public declaration contracts and authored examples. A page can document several related symbols. Implementation bodies are excluded.

pub final class BitSet<A = DefaultAllocator>
    where A: Allocator, Defaultable, Movable

Owns an allocator-aware, densely packed sequence of Boolean bits.

Empty construction allocates nothing. Logical bit indices increase from zero; storage uses 64-bit words with zero unused tail bits. The container is noncopy and moves its allocator and buffer together. Ordinary operations require external synchronization. Every mutation invalidates borrowed cursors. A: Explicit allocator owner; omission selects DefaultAllocator.

Example

module example.bit_set;
from std.collections import BitSet;
from std.memory import DefaultAllocator;
fn Main() -> i32 {
    var Bits = BitSet<DefaultAllocator>.WithAllocator(default(DefaultAllocator));
    if !Bits.IsEmpty { return 1; }
    if Bits.TryReserve(130) is .Err { Error = _ } { return 2; }
    if Bits.TryResize(130) is .Err { Error = _ } { return 3; }
    Bits.Set(0);
    Bits.Set(64);
    if !Bits.Toggle(129) || !Bits.IsSet(64) { return 4; }
    Bits.Reset(0);
    if Bits.CountOnes() != 2 { return 5; }
    {
        var Cursor = Bits.CreateIterator();
        var Ones: usize = 0;
        while Cursor.Next() is .Some { Value = Bit } {
            if Bit { Ones += 1; }
        }
        if Ones != 2 { return 6; }
    }
    Bits.Fill(true);
    if Bits.CountOnes() != 130 { return 7; }
    if Bits.TryResize(65) is .Err { Error = _ } { return 8; }
    if Bits.TryResize(130) is .Err { Error = _ } { return 9; }
    if Bits.IsSet(129) || Bits.CountOnes() != 65 { return 10; }
    var Moved = move(Bits);
    if !Bits.IsEmpty || Moved.Length != 130 { return 11; }
    Bits = move(Moved);
    if !Moved.IsEmpty || Bits.Length != 130 { return 12; }
    Bits.Clear();
    if Bits.TryShrinkToFit() is .Err { Error = _ } { return 13; }
    return 0;
}

BitSet.init

pub init()

Creates an allocation-free empty owner.

BitSet.init

pub init(mut Value: A)

Transfers an allocator into an empty packed owner. Value: Allocator moved without allocation.

BitSet.init

pub init(Source: readonly Self&) = delete;

Rejects copying allocator-owned storage. Source: Owner that cannot be copied.

BitSet.init

pub init(Source: mut Self&&)

Transfers packed storage and leaves the source empty. Source: Writable owner whose buffer and allocator are transferred.

BitSet.operator

pub fn operator =(Source: readonly Self&) -> void = delete;

Rejects copying into existing storage. Source: Owner that cannot be copied. Return: No value; operation is deleted.

BitSet.operator

pub fn operator =(Source: mut Self&&) -> void

Releases previous storage and transfers another packed owner. Source: Writable owner left empty; self-assignment preserves contents. Return: No value; Vector releases the previous allocator-owned storage.

BitSet.WithAllocator

pub static fn WithAllocator(mut Value: A) -> BitSet<A>

Creates an allocation-free owner using a transferred allocator. Value: Allocator transferred into the result. Return: Empty noncopy packed owner.

BitSet.Length

pub Length: usize;

Observes logical bit count in O(1).

BitSet.IsEmpty

pub IsEmpty: bool;

Observes whether no bits are addressable.

BitSet.TryReserve

pub fn TryReserve(MinimumBits: usize) -> Result<void, AllocationError>

Reserves packed capacity without exposing new logical bits. MinimumBits: Minimum desired bit capacity, rounded to packed words. Return: Ok or AllocationError; logical contents and length are unchanged. Warning: May allocate; successful relocation invalidates borrowed cursors.

BitSet.TryResize

pub fn TryResize(NewLength: usize, NewValue: bool)
        -> Result<void, AllocationError>

Changes logical length and initializes all newly exposed bits. NewLength: Desired bit count. NewValue: Initial value for new bits; defaults to false. Return: Ok or AllocationError; failure preserves logical contents/length. Warning: May allocate; invalidates borrowed cursors. O(changed packed words).

BitSet.TryResize

pub fn TryResize(NewLength: usize)
        -> Result<void, AllocationError>

Supplies the omitted arguments to TryResize. Note: Defaults: NewValue = false. NewLength: Same input, ownership and lifetime contract as the full operation. Return: The full synchronous operation's success or typed failure.

BitSet.IsSet

pub readonly fn IsSet(Index: usize) -> bool

Reads one logical bit without allocation. Index: Bit index strictly below Length. Return: Boolean value; an out-of-range index panics.

BitSet.Set

pub fn Set(Index: usize, Value: bool) -> void

Writes one logical bit without allocation. Index: Bit index strictly below Length; out of range panics. Value: New value, defaulting to true. Return: No value; invalidates borrowed cursors.

BitSet.Set

pub fn Set(Index: usize) -> void

Supplies the omitted arguments to Set. Note: Defaults: Value = true. Index: Same input, ownership and lifetime contract as the full operation. Return: No value; applies the full synchronous operation's mutation.

BitSet.Reset

pub fn Reset(Index: usize) -> void

Clears one logical bit without allocation. Index: Bit index strictly below Length; out of range panics. Return: No value; invalidates borrowed cursors.

BitSet.Toggle

pub fn Toggle(Index: usize) -> bool

Inverts one logical bit without allocation. Index: Bit index strictly below Length; out of range panics. Return: New Boolean value; invalidates borrowed cursors.

BitSet.Fill

pub fn Fill(Value: bool) -> void

Writes every logical bit in O(packed word count). Value: New value for all bits. Return: No value; invalidates borrowed cursors and allocates nothing.

BitSet.CountOnes

pub readonly fn CountOnes() -> usize

Counts set bits without allocating. Return: Number of true logical bits; O(words + set bits), at most 64 steps per word.

BitSet.CreateIterator

pub readonly fn CreateIterator() -> BitSetIterator

Borrows packed storage for allocation-free Boolean iteration. Return: Cursor yielding bool values in increasing bit-index order. Warning: Any owner mutation, move or destruction invalidates the cursor.

BitSet.Clear

pub fn Clear() -> void

Removes all logical bits while retaining allocated capacity. Return: No value; invalidates borrowed cursors and allocates nothing.

BitSet.TryShrinkToFit

pub fn TryShrinkToFit() -> Result<void, AllocationError>

Releases excess packed capacity without changing logical bits. Return: Ok or AllocationError; failure preserves logical contents. Warning: May allocate; successful relocation invalidates borrowed cursors.