Module: collections.bitset

Source: ./collections/bitset.reef

Overview

collections/bitset - Efficient Bit Set Data Structure

Provides memory-efficient storage and manipulation of boolean flags. Uses 64-bit integers as storage (1 bit per flag vs 8 bits for bool).

Usage: import collections.bitset

let bs = bitset.create(256) // 256-bit bitset bitset.set_bit(bs, 10) bitset.set_bit(bs, 42)

if bitset.test_bit(bs, 10) println("Bit 10 is set") end if

print("Count: ") print_int(bitset.count_set(bs)) println("")

Use Cases:

• Compiler type qualifiers (const, volatile, etc.)
• Visited node tracking in graph traversal
• Sparse set membership testing
• Feature flag management

Types

BitSet

Fields:

Functions

fn bits_per_word(): int

Bits per word (using 32-bit for portability) Note: Reef's int is 64-bit but overflow occurs at 32 bits in multiplication

fn words_needed(n: int): int

Calculate number of words needed for n bits

fn create(size: int): BitSet

fn create_64(): BitSet

fn create_256(): BitSet

fn create_1024(): BitSet

fn word_index(n: int): int

Get word index for bit n

fn bit_position(n: int): int

Get bit position within word

fn bit_mask(pos: int): int

Create a mask with bit at position set Note: For 64-bit integers, positions 0-63 are valid

fn test_bit(bs: BitSet, n: int): bool

fn count_set(bs: BitSet): int

Simpler popcount using test_bit approach

fn bit_union(a: BitSet, b: BitSet): BitSet

fn bit_intersection(a: BitSet, b: BitSet): BitSet

fn bit_difference(a: BitSet, b: BitSet): BitSet

fn bit_xor(a: BitSet, b: BitSet): BitSet

fn equals(a: BitSet, b: BitSet): bool

fn is_subset(a: BitSet, b: BitSet): bool

fn is_empty(bs: BitSet): bool

fn is_disjoint(a: BitSet, b: BitSet): bool

fn first_set_bit(bs: BitSet): int

fn next_set_bit(bs: BitSet, after: int): int

fn size(bs: BitSet): int

fn word_count(bs: BitSet): int

Procedures

proc set_bit(bs: BitSet, n: int)

proc clear_bit(bs: BitSet, n: int)

proc toggle_bit(bs: BitSet, n: int)

proc set_all(bs: BitSet)

proc clear_all(bs: BitSet)

proc union_into(a: BitSet, b: BitSet)

proc intersection_into(a: BitSet, b: BitSet)

proc difference_into(a: BitSet, b: BitSet)

proc xor_into(a: BitSet, b: BitSet)

Generated by reefc doc