This file defines several variants of bit sets. A bit set is a densely stored set of integers with a known maximum, in which each integer gets a single bit. Bit sets have very fast presence checks, update operations, and union and intersection operations. However, if the number of possible items is very large and the number of actual items in a given set is usually small, they may be less memory efficient than an array set.
There are five variants defined here:
Integer: A bit set with static size, which is backed by a single integer. This set is good for sets with a small size, but may generate inefficient code for larger sets, especially in debug mode.
Array: A bit set with static size, which is backed by an array of usize. This set is good for sets with a larger size, but may use more bytes than necessary if your set is small.
Static: Picks either Integer or Array depending on the requested size. The interfaces of these two types match exactly, except for fields.
Dynamic: A bit set with runtime-known size, backed by an allocated slice of usize.
DynamicManaged: A variant of Dynamic which stores an allocator, using it when needed.
std.bit_set.Allocator
alias
Alias of std.mem.Allocator
std.bit_set.Array
type-function
A bit set with static size, which is backed by an array of usize. This set is good for sets with a larger size, but may use more bytes than necessary if your set is small.
pub fn Array(comptime MaskIntType: type, comptime size: usize) type
Parameters
MaskIntType: type
size: usize
Fields
masks: [num_masks]MaskIntThe bit masks, ordered with lower indices first. Padding bits at the end are undefined.
Selfbit_lengthMaskIntShiftIntmask_lennum_maskslast_pad_bitslast_item_maskemptyfullcapacityisSetcountsetValuesetsetRangeValueunsettoggletoggleSettoggleAllunsetAllsetAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfcomplementunionWithintersectWithxorWithdifferenceWithiteratorIteratormaskBitmaskIndexboolMaskBit
Example usage
test Array {
inline for (.{ 0, 1, 2, 31, 32, 33, 63, 64, 65, 254, 500, 3000 }) |size| {
try testStaticBitSet(Array(u8, size));
try testStaticBitSet(Array(u16, size));
try testStaticBitSet(Array(u32, size));
try testStaticBitSet(Array(u64, size));
try testStaticBitSet(Array(u128, size));
}
}
std.bit_set.Array.bit_length
constant
The number of items in this bit set
usize
std.bit_set.Array.boolMaskBit
function
fn boolMaskBit(index: usize, value: bool) MaskInt
Parameters
index: usize
value: bool
std.bit_set.Array.capacity
function
Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize
Parameters
self: Self
std.bit_set.Array.complement
function
Returns the complement bit sets. Bits in the result are set if the corresponding bits were not set.
pub fn complement(self: Self) Self
Parameters
self: Self
std.bit_set.Array.count
function
Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize
Parameters
self: Self
std.bit_set.Array.differenceWith
function
Returns the difference of two bit sets. Bits in the result are set if set in the first but not set in the second set.
pub fn differenceWith(self: Self, other: Self) Self
Parameters
std.bit_set.Array.empty
constant
A bit set with no elements present.
Self
std.bit_set.Array.eql
function
Returns true iff every corresponding bit in both bit sets are the same.
pub fn eql(self: Self, other: Self) bool
Parameters
std.bit_set.Array.findFirstSet
function
Finds the index of the first set bit. If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Array.findLastSet
function
Finds the index of the last set bit. If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Array.full
constant
A bit set with all elements present.
Self
std.bit_set.Array.intersectWith
function
Returns the intersection of two bit sets. Bits in the result are set if the corresponding bits were set in both inputs.
pub fn intersectWith(self: Self, other: Self) Self
Parameters
std.bit_set.Array.isSet
function
Returns true if the bit at the specified index is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool
Parameters
self: Self
index: usize
std.bit_set.Array.iterator
function
Iterates through the items in the set, according to the options. The default options (.{}) will iterate indices of set bits in ascending order. Modifications to the underlying bit set may or may not be observed by the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
Parameters
self: *const Self
options: IteratorOptions
std.bit_set.Array.Iterator
type-function
pub fn Iterator(comptime options: IteratorOptions) type
Parameters
options: IteratorOptions
std.bit_set.Array.last_item_mask
constant
std.bit_set.Array.last_pad_bits
constant
std.bit_set.Array.mask_len
constant
std.bit_set.Array.maskBit
function
fn maskBit(index: usize) MaskInt
Parameters
index: usize
std.bit_set.Array.maskIndex
function
fn maskIndex(index: usize) usize
Parameters
index: usize
std.bit_set.Array.MaskInt
constant
The integer type used to represent a mask in this bit set
std.bit_set.Array.num_masks
constant
std.bit_set.Array.Self
alias
Alias of std.bit_set.Array
std.bit_set.Array.set
function
Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Array.setAll
function
Set all bits to 1.
pub fn setAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Array.setIntersection
function
Performs an intersection of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in both inputs.
pub fn setIntersection(self: *Self, other: Self) void
Parameters
std.bit_set.Array.setRangeValue
function
Changes the value of all bits in the specified range to match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
Parameters
std.bit_set.Array.setUnion
function
Performs a union of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in either input.
pub fn setUnion(self: *Self, other: Self) void
Parameters
std.bit_set.Array.setValue
function
Changes the value of the specified bit of the bit set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void
Parameters
std.bit_set.Array.ShiftInt
type
The integer type used to shift a mask in this bit set
std.bit_set.Array.subsetOf
function
Returns true iff the first bit set is the subset of the second one.
pub fn subsetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Array.supersetOf
function
Returns true iff the first bit set is the superset of the second one.
pub fn supersetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Array.toggle
function
Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Array.toggleAll
function
Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Array.toggleFirstSet
function
Finds the index of the first set bit, and unsets it. If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize
Parameters
self: *Self
std.bit_set.Array.toggleSet
function
Flips all bits in this bit set which are present in the toggles bit set.
pub fn toggleSet(self: *Self, toggles: Self) void
Parameters
std.bit_set.Array.unionWith
function
Returns the union of two bit sets. Bits in the result are set if the corresponding bits were set in either input.
pub fn unionWith(self: Self, other: Self) Self
Parameters
std.bit_set.Array.unset
function
Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Array.unsetAll
function
Set all bits to 0.
pub fn unsetAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Array.xorWith
function
Returns the xor of two bit sets. Bits in the result are set if the corresponding bits were not the same in both inputs.
pub fn xorWith(self: Self, other: Self) Self
Parameters
std.bit_set.ArrayBitSet
alias
Deprecated: use Array.
Alias of std.bit_set.Array
std.bit_set.assert
alias
Alias of std.debug.assert
std.bit_set.builtin
constant
std.bit_set.Dynamic
container
A bit set with runtime-known size, backed by an allocated slice of usize. The allocator must be tracked externally by the user.
Fields
bit_length: usize = 0The number of valid items in this bit set
masks: [*]MaskInt = empty_masks_ptrThe bit masks, ordered with lower indices first. Padding bits at the end must be zeroed.
SelfMaskIntShiftIntempty_masks_dataempty_masks_ptrinitEmptyinitFullresizedeinitclonecapacityisSetcountsetValuesetsetRangeValueunsetunsetAllsetAlltoggletoggleSettoggleAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfiteratorIteratormaskBitmaskIndexboolMaskBitnumMasks
std.bit_set.Dynamic.boolMaskBit
function
fn boolMaskBit(index: usize, value: bool) MaskInt
Parameters
index: usize
value: bool
std.bit_set.Dynamic.capacity
function
Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize
Parameters
self: Self
std.bit_set.Dynamic.clone
function
Creates a duplicate of this bit set, using the new allocator.
pub fn clone(self: *const Self, new_allocator: Allocator) !Self
Parameters
std.bit_set.Dynamic.count
function
Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize
Parameters
self: Self
std.bit_set.Dynamic.deinit
function
Deinitializes the array and releases its memory. The passed allocator must be the same one used for init* or resize in the past.
pub fn deinit(self: *Self, allocator: Allocator) void
Parameters
std.bit_set.Dynamic.empty_masks_data
constant
std.bit_set.Dynamic.empty_masks_ptr
constant
std.bit_set.Dynamic.eql
function
Returns true iff every corresponding bit in both bit sets are the same.
pub fn eql(self: Self, other: Self) bool
Parameters
std.bit_set.Dynamic.findFirstSet
function
Finds the index of the first set bit. If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Dynamic.findLastSet
function
Finds the index of the last set bit. If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Dynamic.initEmpty
function
Creates a bit set with no elements present. If bit_length is not zero, deinit must eventually be called.
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self
Parameters
allocator: Allocator
bit_length: usize
std.bit_set.Dynamic.initFull
function
Creates a bit set with all elements present. If bit_length is not zero, deinit must eventually be called.
pub fn initFull(allocator: Allocator, bit_length: usize) !Self
Parameters
allocator: Allocator
bit_length: usize
std.bit_set.Dynamic.isSet
function
Returns true if the bit at the specified index is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool
Parameters
self: Self
index: usize
std.bit_set.Dynamic.iterator
function
Iterates through the items in the set, according to the options. The default options (.{}) will iterate indices of set bits in ascending order. Modifications to the underlying bit set may or may not be observed by the iterator. Resizing the underlying bit set invalidates the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
Parameters
self: *const Self
options: IteratorOptions
std.bit_set.Dynamic.Iterator
type-function
pub fn Iterator(comptime options: IteratorOptions) type
Parameters
options: IteratorOptions
std.bit_set.Dynamic.maskBit
function
fn maskBit(index: usize) MaskInt
Parameters
index: usize
std.bit_set.Dynamic.maskIndex
function
fn maskIndex(index: usize) usize
Parameters
index: usize
std.bit_set.Dynamic.MaskInt
type
The integer type used to represent a mask in this bit set
std.bit_set.Dynamic.numMasks
function
fn numMasks(bit_length: usize) usize
Parameters
bit_length: usize
std.bit_set.Dynamic.resize
function
Resizes to a new bit_length. If the new length is larger
than the old length, fills any added bits with fill.
If new_len is not zero, deinit must eventually be called.
pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void
Parameters
std.bit_set.Dynamic.Self
alias
Alias of std.bit_set.Dynamic
std.bit_set.Dynamic.set
function
Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Dynamic.setAll
function
Set all bits to 1.
pub fn setAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Dynamic.setIntersection
function
Performs an intersection of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in both inputs. The two sets must both be the same bit_length.
pub fn setIntersection(self: *Self, other: Self) void
Parameters
std.bit_set.Dynamic.setRangeValue
function
Changes the value of all bits in the specified range to match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
Parameters
std.bit_set.Dynamic.setUnion
function
Performs a union of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in either input. The two sets must both be the same bit_length.
pub fn setUnion(self: *Self, other: Self) void
Parameters
std.bit_set.Dynamic.setValue
function
Changes the value of the specified bit of the bit set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void
Parameters
std.bit_set.Dynamic.ShiftInt
type
The integer type used to shift a mask in this bit set
std.bit_set.Dynamic.subsetOf
function
Returns true iff the first bit set is the subset of the second one.
pub fn subsetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Dynamic.supersetOf
function
Returns true iff the first bit set is the superset of the second one.
pub fn supersetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Dynamic.toggle
function
Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Dynamic.toggleAll
function
Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Dynamic.toggleFirstSet
function
Finds the index of the first set bit, and unsets it. If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize
Parameters
self: *Self
std.bit_set.Dynamic.toggleSet
function
Flips all bits in this bit set which are present in the toggles bit set. Both sets must have the same bit_length.
pub fn toggleSet(self: *Self, toggles: Self) void
Parameters
std.bit_set.Dynamic.unset
function
Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Dynamic.unsetAll
function
Set all bits to 0.
pub fn unsetAll(self: *Self) void
Parameters
self: *Self
std.bit_set.DynamicBitSet
alias
Deprecated: use DynamicManaged or Dynamic (will need to update callsites).
Alias of std.bit_set.DynamicManaged
std.bit_set.DynamicBitSetUnmanaged
alias
Deprecated: use Dynamic.
Alias of std.bit_set.Dynamic
std.bit_set.DynamicManaged
container
A bit set with runtime-known size, backed by an allocated slice of usize. Thin wrapper around Dynamic which keeps track of the allocator instance.
Deprecated in favor of Dynamic which accepts an Allocator
as a parameter when needed instead of storing it.
Fields
std.bit_set.DynamicManaged.capacity
function
Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize
Parameters
self: Self
std.bit_set.DynamicManaged.clone
function
Creates a duplicate of this bit set, using the new allocator.
pub fn clone(self: *const Self, new_allocator: Allocator) !Self
Parameters
std.bit_set.DynamicManaged.count
function
Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize
Parameters
self: Self
std.bit_set.DynamicManaged.deinit
function
Deinitializes the array and releases its memory. The passed allocator must be the same one used for init* or resize in the past.
pub fn deinit(self: *Self) void
Parameters
self: *Self
std.bit_set.DynamicManaged.eql
function
Returns true iff every corresponding bit in both bit sets are the same.
pub fn eql(self: Self, other: Self) bool
Parameters
std.bit_set.DynamicManaged.findFirstSet
function
Finds the index of the first set bit. If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.DynamicManaged.findLastSet
function
Finds the index of the last set bit. If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.DynamicManaged.initEmpty
function
Creates a bit set with no elements present.
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self
Parameters
allocator: Allocator
bit_length: usize
std.bit_set.DynamicManaged.initFull
function
Creates a bit set with all elements present.
pub fn initFull(allocator: Allocator, bit_length: usize) !Self
Parameters
allocator: Allocator
bit_length: usize
std.bit_set.DynamicManaged.isSet
function
Returns true if the bit at the specified index is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool
Parameters
self: Self
index: usize
std.bit_set.DynamicManaged.iterator
function
Iterates through the items in the set, according to the options. The default options (.{}) will iterate indices of set bits in ascending order. Modifications to the underlying bit set may or may not be observed by the iterator. Resizing the underlying bit set invalidates the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
Parameters
self: *const Self
options: IteratorOptions
std.bit_set.DynamicManaged.Iterator
alias
Alias of std.bit_set.Dynamic.Iterator
std.bit_set.DynamicManaged.MaskInt
type
The integer type used to represent a mask in this bit set
std.bit_set.DynamicManaged.resize
function
Resizes to a new length. If the new length is larger
than the old length, fills any added bits with fill.
pub fn resize(self: *@This(), new_len: usize, fill: bool) !void
Parameters
self: *@This()
new_len: usize
fill: bool
std.bit_set.DynamicManaged.Self
alias
Alias of std.bit_set.DynamicManaged
std.bit_set.DynamicManaged.set
function
Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.DynamicManaged.setAll
function
Set all bits to 1.
pub fn setAll(self: *Self) void
Parameters
self: *Self
std.bit_set.DynamicManaged.setIntersection
function
Performs an intersection of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in both inputs. The two sets must both be the same bit_length.
pub fn setIntersection(self: *Self, other: Self) void
Parameters
std.bit_set.DynamicManaged.setRangeValue
function
Changes the value of all bits in the specified range to match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
Parameters
std.bit_set.DynamicManaged.setUnion
function
Performs a union of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in either input. The two sets must both be the same bit_length.
pub fn setUnion(self: *Self, other: Self) void
Parameters
std.bit_set.DynamicManaged.setValue
function
Changes the value of the specified bit of the bit set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void
Parameters
std.bit_set.DynamicManaged.ShiftInt
type
The integer type used to shift a mask in this bit set
std.bit_set.DynamicManaged.toggle
function
Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.DynamicManaged.toggleAll
function
Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void
Parameters
self: *Self
std.bit_set.DynamicManaged.toggleFirstSet
function
Finds the index of the first set bit, and unsets it. If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize
Parameters
self: *Self
std.bit_set.DynamicManaged.toggleSet
function
Flips all bits in this bit set which are present in the toggles bit set. Both sets must have the same bit_length.
pub fn toggleSet(self: *Self, toggles: Self) void
Parameters
std.bit_set.DynamicManaged.unset
function
Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.DynamicManaged.unsetAll
function
Set all bits to 0.
pub fn unsetAll(self: *Self) void
Parameters
self: *Self
std.bit_set.fillEven
function
fn fillEven(set: anytype, len: usize) void
Parameters
len: usize
std.bit_set.fillOdd
function
fn fillOdd(set: anytype, len: usize) void
Parameters
len: usize
std.bit_set.GenericIterator
type-function
fn GenericIterator(comptime MaskInt: type, comptime options: IteratorOptions) type
Parameters
MaskInt: type
options: IteratorOptions
Fields
bits_remain: MaskInt
words_remain: []const MaskInt
bit_offset: usize
last_word_mask: MaskInt
std.bit_set.GenericIterator.init
function
fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self
Parameters
masks: []const MaskInt
last_word_mask: MaskInt
std.bit_set.GenericIterator.next
function
Returns the index of the next unvisited set bit in the bit set, in ascending order.
pub fn next(self: *Self) ?usize
Parameters
self: *Self
std.bit_set.GenericIterator.nextWord
function
inline fn nextWord(self: *Self, comptime is_first_word: bool) void
Parameters
self: *Self
is_first_word: bool
std.bit_set.GenericIterator.Self
alias
Alias of std.bit_set.GenericIterator
std.bit_set.Integer
type-function
A bit set with static size, which is backed by a single integer. This set is good for sets with a small size, but may generate inefficient code for larger sets, especially in debug mode.
pub fn Integer(comptime size: u16) type
Parameters
size: u16
Fields
mask: MaskIntThe bit mask, as a single integer
Selfbit_lengthMaskIntShiftIntemptyfullcapacityisSetcountsetValuesetsetRangeValueunsettoggletoggleSettoggleAllunsetAllsetAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfcomplementunionWithintersectWithxorWithdifferenceWithiteratorIteratorSingleWordIteratormaskBitboolMaskBit
Example usage
test Integer {
try testStaticBitSet(Integer(0));
try testStaticBitSet(Integer(1));
try testStaticBitSet(Integer(2));
try testStaticBitSet(Integer(5));
try testStaticBitSet(Integer(8));
try testStaticBitSet(Integer(32));
try testStaticBitSet(Integer(64));
try testStaticBitSet(Integer(127));
}
std.bit_set.Integer.bit_length
constant
The number of items in this bit set
usize
std.bit_set.Integer.boolMaskBit
function
fn boolMaskBit(index: usize, value: bool) MaskInt
Parameters
index: usize
value: bool
std.bit_set.Integer.capacity
function
Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize
Parameters
self: Self
std.bit_set.Integer.complement
function
Returns the complement bit sets. Bits in the result are set if the corresponding bits were not set.
pub fn complement(self: Self) Self
Parameters
self: Self
std.bit_set.Integer.count
function
Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize
Parameters
self: Self
std.bit_set.Integer.differenceWith
function
Returns the difference of two bit sets. Bits in the result are set if set in the first but not set in the second set.
pub fn differenceWith(self: Self, other: Self) Self
Parameters
std.bit_set.Integer.empty
constant
A bit set with no elements present.
Self
std.bit_set.Integer.eql
function
Returns true iff every corresponding bit in both bit sets are the same.
pub fn eql(self: Self, other: Self) bool
Parameters
std.bit_set.Integer.findFirstSet
function
Finds the index of the first set bit. If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Integer.findLastSet
function
Finds the index of the last set bit. If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize
Parameters
self: Self
std.bit_set.Integer.full
constant
A bit set with all elements present.
Self
std.bit_set.Integer.intersectWith
function
Returns the intersection of two bit sets. Bits in the result are set if the corresponding bits were set in both inputs.
pub fn intersectWith(self: Self, other: Self) Self
Parameters
std.bit_set.Integer.isSet
function
Returns true if the bit at the specified index is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool
Parameters
self: Self
index: usize
std.bit_set.Integer.iterator
function
Iterates through the items in the set, according to the options. The default options (.{}) will iterate indices of set bits in ascending order. Modifications to the underlying bit set may or may not be observed by the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
Parameters
self: *const Self
options: IteratorOptions
std.bit_set.Integer.Iterator
type-function
pub fn Iterator(comptime options: IteratorOptions) type
Parameters
options: IteratorOptions
std.bit_set.Integer.maskBit
function
fn maskBit(index: usize) MaskInt
Parameters
index: usize
std.bit_set.Integer.MaskInt
constant
The integer type used to represent a mask in this bit set
std.bit_set.Integer.Self
alias
Alias of std.bit_set.Integer
std.bit_set.Integer.set
function
Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Integer.setAll
function
Set all bits to 1.
pub fn setAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Integer.setIntersection
function
Performs an intersection of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in both inputs.
pub fn setIntersection(self: *Self, other: Self) void
Parameters
std.bit_set.Integer.setRangeValue
function
Changes the value of all bits in the specified range to match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
Parameters
std.bit_set.Integer.setUnion
function
Performs a union of two bit sets, and stores the result in the first one. Bits in the result are set if the corresponding bits were set in either input.
pub fn setUnion(self: *Self, other: Self) void
Parameters
std.bit_set.Integer.setValue
function
Changes the value of the specified bit of the bit set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void
Parameters
std.bit_set.Integer.ShiftInt
type
The integer type used to shift a mask in this bit set
std.bit_set.Integer.SingleWordIterator
type-function
fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type
Parameters
direction: IteratorOptions.Direction
Fields
bits_remain: MaskInt
std.bit_set.Integer.SingleWordIterator.IterSelf
alias
std.bit_set.Integer.SingleWordIterator.next
function
Returns the index of the next unvisited set bit in the bit set, in ascending order.
pub fn next(self: *IterSelf) ?usize
Parameters
self: *IterSelf
std.bit_set.Integer.subsetOf
function
Returns true iff the first bit set is the subset of the second one.
pub fn subsetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Integer.supersetOf
function
Returns true iff the first bit set is the superset of the second one.
pub fn supersetOf(self: Self, other: Self) bool
Parameters
std.bit_set.Integer.toggle
function
Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Integer.toggleAll
function
Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Integer.toggleFirstSet
function
Finds the index of the first set bit, and unsets it. If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize
Parameters
self: *Self
std.bit_set.Integer.toggleSet
function
Flips all bits in this bit set which are present in the toggles bit set.
pub fn toggleSet(self: *Self, toggles: Self) void
Parameters
std.bit_set.Integer.unionWith
function
Returns the union of two bit sets. Bits in the result are set if the corresponding bits were set in either input.
pub fn unionWith(self: Self, other: Self) Self
Parameters
std.bit_set.Integer.unset
function
Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void
Parameters
self: *Self
index: usize
std.bit_set.Integer.unsetAll
function
Set all bits to 0.
pub fn unsetAll(self: *Self) void
Parameters
self: *Self
std.bit_set.Integer.xorWith
function
Returns the xor of two bit sets. Bits in the result are set if the corresponding bits were not the same in both inputs.
pub fn xorWith(self: Self, other: Self) Self
Parameters
std.bit_set.IntegerBitSet
alias
Deprecated: use Integer.
Alias of std.bit_set.Integer
std.bit_set.IteratorOptions
container
Options for configuring an iterator over a bit set
Fields
std.bit_set.IteratorOptions.Direction
container
Fields
forwardvisit indices in ascending order
reversevisit indices in descending order. Note that this may be slightly more expensive than forward iteration.
std.bit_set.IteratorOptions.Type
container
Fields
setvisit indexes of set bits
unsetvisit indexes of unset bits
std.bit_set.Range
container
A range of indices within a bitset.
Fields
start: usizeThe index of the first bit of interest.
end: usizeThe index immediately after the last bit of interest.
std.bit_set.Static
type-function
Returns the optimal static bit set type for the specified number
of elements: either IntegerBitSet or ArrayBitSet,
both of which fulfill the same interface.
The returned type will perform no allocations,
can be copied by value, and does not require deinitialization.
pub fn Static(comptime size: usize) type
Parameters
size: usize
Example usage
test Static {
try testing.expectEqual(Integer(0), Static(0));
try testing.expectEqual(Integer(5), Static(5));
try testing.expectEqual(Integer(@bitSizeOf(usize)), Static(@bitSizeOf(usize)));
try testing.expectEqual(Array(usize, @bitSizeOf(usize) + 1), Static(@bitSizeOf(usize) + 1));
try testing.expectEqual(Array(usize, 500), Static(500));
}
std.bit_set.StaticBitSet
alias
Deprecated: use Static.
Alias of std.bit_set.Static
std.bit_set.std
alias
Alias of std
std.bit_set.testBitSet
function
fn testBitSet(a: anytype, b: anytype, len: usize) !void
Parameters
len: usize
std.bit_set.testEql
function
fn testEql(empty: anytype, full: anytype, len: usize) !void
Parameters
len: usize
std.bit_set.testing
alias
Alias of std.testing
std.bit_set.testPureBitSet
function
fn testPureBitSet(comptime Set: type) !void
Parameters
Set: type
std.bit_set.testStaticBitSet
function
fn testStaticBitSet(comptime Set: type) !void
Parameters
Set: type
std.bit_set.testSubsetOf
function
fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void
Parameters
len: usize
std.bit_set.testSupersetOf
function
fn testSupersetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void
Parameters
len: usize
Source code
std/bit_set.zig
//! This file defines several variants of bit sets. A bit set
//! is a densely stored set of integers with a known maximum,
//! in which each integer gets a single bit. Bit sets have very
//! fast presence checks, update operations, and union and intersection
//! operations. However, if the number of possible items is very
//! large and the number of actual items in a given set is usually
//! small, they may be less memory efficient than an array set.
//!
//! There are five variants defined here:
//!
//! Integer:
//! A bit set with static size, which is backed by a single integer.
//! This set is good for sets with a small size, but may generate
//! inefficient code for larger sets, especially in debug mode.
//!
//! Array:
//! A bit set with static size, which is backed by an array of usize.
//! This set is good for sets with a larger size, but may use
//! more bytes than necessary if your set is small.
//!
//! Static:
//! Picks either Integer or Array depending on the requested
//! size. The interfaces of these two types match exactly, except for fields.
//!
//! Dynamic:
//! A bit set with runtime-known size, backed by an allocated slice
//! of usize.
//!
//! DynamicManaged:
//! A variant of Dynamic which stores an allocator, using it when needed.
const std = @import("std.zig");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
const builtin = @import("builtin");
/// Deprecated: use `Static`.
pub const StaticBitSet = Static;
/// Returns the optimal static bit set type for the specified number
/// of elements: either `IntegerBitSet` or `ArrayBitSet`,
/// both of which fulfill the same interface.
/// The returned type will perform no allocations,
/// can be copied by value, and does not require deinitialization.
pub fn Static(comptime size: usize) type {
if (size <= @bitSizeOf(usize)) {
return Integer(size);
} else {
return Array(usize, size);
}
}
/// Deprecated: use `Integer`.
pub const IntegerBitSet = Integer;
/// A bit set with static size, which is backed by a single integer.
/// This set is good for sets with a small size, but may generate
/// inefficient code for larger sets, especially in debug mode.
pub fn Integer(comptime size: u16) type {
return packed struct(MaskInt) {
const Self = @This();
// TODO: Make this a comptime field once those are fixed
/// The number of items in this bit set
pub const bit_length: usize = size;
/// The integer type used to represent a mask in this bit set
pub const MaskInt = @Int(.unsigned, size);
/// The integer type used to shift a mask in this bit set
pub const ShiftInt = std.math.Log2Int(MaskInt);
/// The bit mask, as a single integer
mask: MaskInt,
/// A bit set with no elements present.
pub const empty: Self = .{ .mask = 0 };
/// A bit set with all elements present.
pub const full: Self = .{ .mask = ~@as(MaskInt, 0) };
/// Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize {
_ = self;
return bit_length;
}
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
assert(index < bit_length);
return (self.mask & maskBit(index)) != 0;
}
/// Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize {
return @popCount(self.mask);
}
/// Changes the value of the specified bit of the bit
/// set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void {
assert(index < bit_length);
if (MaskInt == u0) return;
const bit = maskBit(index);
const new_bit = bit & std.math.boolMask(MaskInt, value);
self.mask = (self.mask & ~bit) | new_bit;
}
/// Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void {
assert(index < bit_length);
self.mask |= maskBit(index);
}
/// Changes the value of all bits in the specified range to
/// match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
assert(range.end <= bit_length);
assert(range.start <= range.end);
if (range.start == range.end) return;
if (MaskInt == u0) return;
const start_bit = @as(ShiftInt, @intCast(range.start));
var mask = std.math.boolMask(MaskInt, true) << start_bit;
if (range.end != bit_length) {
const end_bit = @as(ShiftInt, @intCast(range.end));
mask &= std.math.boolMask(MaskInt, true) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit)));
}
self.mask &= ~mask;
mask = std.math.boolMask(MaskInt, value) << start_bit;
if (range.end != bit_length) {
const end_bit = @as(ShiftInt, @intCast(range.end));
mask &= std.math.boolMask(MaskInt, value) >> @as(ShiftInt, @truncate(@as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit)));
}
self.mask |= mask;
}
/// Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void {
assert(index < bit_length);
// Workaround for #7953
if (MaskInt == u0) return;
self.mask &= ~maskBit(index);
}
/// Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void {
assert(index < bit_length);
self.mask ^= maskBit(index);
}
/// Flips all bits in this bit set which are present
/// in the toggles bit set.
pub fn toggleSet(self: *Self, toggles: Self) void {
self.mask ^= toggles.mask;
}
/// Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void {
self.mask = ~self.mask;
}
/// Set all bits to 0.
pub fn unsetAll(self: *Self) void {
self.mask = 0;
}
/// Set all bits to 1.
pub fn setAll(self: *Self) void {
self.mask = ~@as(MaskInt, 0);
}
/// Performs a union of two bit sets, and stores the
/// result in the first one. Bits in the result are
/// set if the corresponding bits were set in either input.
pub fn setUnion(self: *Self, other: Self) void {
self.mask |= other.mask;
}
/// Performs an intersection of two bit sets, and stores
/// the result in the first one. Bits in the result are
/// set if the corresponding bits were set in both inputs.
pub fn setIntersection(self: *Self, other: Self) void {
self.mask &= other.mask;
}
/// Finds the index of the first set bit.
/// If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize {
const mask = self.mask;
if (mask == 0) return null;
return @ctz(mask);
}
/// Finds the index of the last set bit.
/// If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize {
const mask = self.mask;
if (mask == 0) return null;
return bit_length - @clz(mask) - 1;
}
/// Finds the index of the first set bit, and unsets it.
/// If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize {
const mask = self.mask;
if (mask == 0) return null;
const index = @ctz(mask);
self.mask = mask & (mask - 1);
return index;
}
/// Returns true iff every corresponding bit in both
/// bit sets are the same.
pub fn eql(self: Self, other: Self) bool {
return bit_length == 0 or self.mask == other.mask;
}
/// Returns true iff the first bit set is the subset
/// of the second one.
pub fn subsetOf(self: Self, other: Self) bool {
return self.intersectWith(other).eql(self);
}
/// Returns true iff the first bit set is the superset
/// of the second one.
pub fn supersetOf(self: Self, other: Self) bool {
return other.subsetOf(self);
}
/// Returns the complement bit sets. Bits in the result
/// are set if the corresponding bits were not set.
pub fn complement(self: Self) Self {
var result = self;
result.toggleAll();
return result;
}
/// Returns the union of two bit sets. Bits in the
/// result are set if the corresponding bits were set
/// in either input.
pub fn unionWith(self: Self, other: Self) Self {
var result = self;
result.setUnion(other);
return result;
}
/// Returns the intersection of two bit sets. Bits in
/// the result are set if the corresponding bits were
/// set in both inputs.
pub fn intersectWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other);
return result;
}
/// Returns the xor of two bit sets. Bits in the
/// result are set if the corresponding bits were
/// not the same in both inputs.
pub fn xorWith(self: Self, other: Self) Self {
var result = self;
result.toggleSet(other);
return result;
}
/// Returns the difference of two bit sets. Bits in
/// the result are set if set in the first but not
/// set in the second set.
pub fn differenceWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other.complement());
return result;
}
/// Iterates through the items in the set, according to the options.
/// The default options (.{}) will iterate indices of set bits in
/// ascending order. Modifications to the underlying bit set may
/// or may not be observed by the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
return .{
.bits_remain = switch (options.kind) {
.set => self.mask,
.unset => ~self.mask,
},
};
}
pub fn Iterator(comptime options: IteratorOptions) type {
return SingleWordIterator(options.direction);
}
fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type {
return struct {
const IterSelf = @This();
// all bits which have not yet been iterated over
bits_remain: MaskInt,
/// Returns the index of the next unvisited set bit
/// in the bit set, in ascending order.
pub fn next(self: *IterSelf) ?usize {
if (self.bits_remain == 0) return null;
switch (direction) {
.forward => {
const next_index = @ctz(self.bits_remain);
self.bits_remain &= self.bits_remain - 1;
return next_index;
},
.reverse => {
const leading_zeroes = @clz(self.bits_remain);
const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
self.bits_remain &= (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1;
return top_bit;
},
}
}
};
}
fn maskBit(index: usize) MaskInt {
if (MaskInt == u0) return 0;
return @as(MaskInt, 1) << @as(ShiftInt, @intCast(index));
}
fn boolMaskBit(index: usize, value: bool) MaskInt {
if (MaskInt == u0) return 0;
return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
}
};
}
/// Deprecated: use `Array`.
pub const ArrayBitSet = Array;
/// A bit set with static size, which is backed by an array of usize.
/// This set is good for sets with a larger size, but may use
/// more bytes than necessary if your set is small.
pub fn Array(comptime MaskIntType: type, comptime size: usize) type {
const mask_info: std.builtin.Type = @typeInfo(MaskIntType);
// Make sure the mask int is indeed an int
if (mask_info != .int) @compileError("Array can only operate on integer masks, but was passed " ++ @typeName(MaskIntType));
// It must also be unsigned.
if (mask_info.int.signedness != .unsigned) @compileError("Array requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType));
// And it must not be empty.
if (MaskIntType == u0)
@compileError("Array requires a sized integer for its mask int. u0 does not work.");
const byte_size = std.mem.byte_size_in_bits;
// We use shift and truncate to decompose indices into mask indices and bit indices.
// This operation requires that the mask has an exact power of two number of bits.
if (!std.math.isPowerOfTwo(@bitSizeOf(MaskIntType))) {
var desired_bits = std.math.ceilPowerOfTwoAssert(usize, @bitSizeOf(MaskIntType));
if (desired_bits < byte_size) desired_bits = byte_size;
const FixedMaskType = @Int(.unsigned, desired_bits);
@compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++
", which is not a power of two. Please round this up to a power of two integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
}
// Make sure the integer has no padding bits.
// Those would be wasteful here and are probably a mistake by the user.
// This case may be hit with small powers of two, like u4.
if (@bitSizeOf(MaskIntType) != @sizeOf(MaskIntType) * byte_size) {
var desired_bits = @sizeOf(MaskIntType) * byte_size;
desired_bits = std.math.ceilPowerOfTwoAssert(usize, desired_bits);
const FixedMaskType = @Int(.unsigned, desired_bits);
@compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++
", which contains padding bits. Please round this up to an unpadded integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
}
return extern struct {
const Self = @This();
// TODO: Make this a comptime field once those are fixed
/// The number of items in this bit set
pub const bit_length: usize = size;
/// The integer type used to represent a mask in this bit set
pub const MaskInt = MaskIntType;
/// The integer type used to shift a mask in this bit set
pub const ShiftInt = std.math.Log2Int(MaskInt);
// bits in one mask
const mask_len = @bitSizeOf(MaskInt);
// total number of masks
const num_masks = (size + mask_len - 1) / mask_len;
// padding bits in the last mask (may be 0)
const last_pad_bits = mask_len * num_masks - size;
// Mask of valid bits in the last mask.
// All functions will ensure that the invalid
// bits in the last mask are zero.
pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits;
/// The bit masks, ordered with lower indices first.
/// Padding bits at the end are undefined.
masks: [num_masks]MaskInt,
/// A bit set with no elements present.
pub const empty: Self = .{ .masks = @splat(0) };
/// A bit set with all elements present.
pub const full: Self = full: {
var masks: [num_masks]MaskInt = @splat(~@as(MaskInt, 0));
if (num_masks > 0) masks[num_masks - 1] = last_item_mask;
break :full .{ .masks = masks };
};
/// Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize {
_ = self;
return bit_length;
}
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
assert(index < bit_length);
if (num_masks == 0) return false; // doesn't compile in this case
return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
}
/// Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize {
var total: usize = 0;
for (self.masks) |mask| {
total += @popCount(mask);
}
return total;
}
/// Changes the value of the specified bit of the bit
/// set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
const bit = maskBit(index);
const mask_index = maskIndex(index);
const new_bit = bit & std.math.boolMask(MaskInt, value);
self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
}
/// Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] |= maskBit(index);
}
/// Changes the value of all bits in the specified range to
/// match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
assert(range.end <= bit_length);
assert(range.start <= range.end);
if (range.start == range.end) return;
if (num_masks == 0) return;
const start_mask_index = maskIndex(range.start);
const start_bit = @as(ShiftInt, @truncate(range.start));
const end_mask_index = maskIndex(range.end);
const end_bit = @as(ShiftInt, @truncate(range.end));
if (start_mask_index == end_mask_index) {
var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
var mask2 = std.math.boolMask(MaskInt, true) >> (mask_len - 1) - (end_bit - 1);
self.masks[start_mask_index] &= ~(mask1 & mask2);
mask1 = std.math.boolMask(MaskInt, value) << start_bit;
mask2 = std.math.boolMask(MaskInt, value) >> (mask_len - 1) - (end_bit - 1);
self.masks[start_mask_index] |= mask1 & mask2;
} else {
var bulk_mask_index: usize = undefined;
if (start_bit > 0) {
self.masks[start_mask_index] =
(self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
(std.math.boolMask(MaskInt, value) << start_bit);
bulk_mask_index = start_mask_index + 1;
} else {
bulk_mask_index = start_mask_index;
}
while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
}
if (end_bit > 0) {
self.masks[end_mask_index] =
(self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
(std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
}
}
}
/// Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] &= ~maskBit(index);
}
/// Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] ^= maskBit(index);
}
/// Flips all bits in this bit set which are present
/// in the toggles bit set.
pub fn toggleSet(self: *Self, toggles: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* ^= toggles.masks[i];
}
}
/// Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void {
for (&self.masks) |*mask| {
mask.* = ~mask.*;
}
// Zero the padding bits
if (num_masks > 0) {
self.masks[num_masks - 1] &= last_item_mask;
}
}
/// Set all bits to 0.
pub fn unsetAll(self: *Self) void {
for (&self.masks) |*mask| {
mask.* = 0;
}
}
/// Set all bits to 1.
pub fn setAll(self: *Self) void {
for (&self.masks) |*mask| {
mask.* = ~@as(MaskInt, 0);
}
if (num_masks > 0) {
self.masks[num_masks - 1] &= last_item_mask;
}
}
/// Performs a union of two bit sets, and stores the
/// result in the first one. Bits in the result are
/// set if the corresponding bits were set in either input.
pub fn setUnion(self: *Self, other: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* |= other.masks[i];
}
}
/// Performs an intersection of two bit sets, and stores
/// the result in the first one. Bits in the result are
/// set if the corresponding bits were set in both inputs.
pub fn setIntersection(self: *Self, other: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* &= other.masks[i];
}
}
/// Finds the index of the first set bit.
/// If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize {
var offset: usize = 0;
const mask = for (self.masks) |mask| {
if (mask != 0) break mask;
offset += @bitSizeOf(MaskInt);
} else return null;
return offset + @ctz(mask);
}
/// Finds the index of the last set bit.
/// If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize {
if (bit_length == 0) return null;
const bs = @bitSizeOf(MaskInt);
var len = bit_length / bs;
if (bit_length % bs != 0) len += 1;
var offset: usize = len * bs;
var idx: usize = len - 1;
while (self.masks[idx] == 0) : (idx -= 1) {
offset -= bs;
if (idx == 0) return null;
}
offset -= @clz(self.masks[idx]);
offset -= 1;
return offset;
}
/// Finds the index of the first set bit, and unsets it.
/// If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize {
var offset: usize = 0;
const mask = for (&self.masks) |*mask| {
if (mask.* != 0) break mask;
offset += @bitSizeOf(MaskInt);
} else return null;
const index = @ctz(mask.*);
mask.* &= (mask.* - 1);
return offset + index;
}
/// Returns true iff every corresponding bit in both
/// bit sets are the same.
pub fn eql(self: Self, other: Self) bool {
var i: usize = 0;
return while (i < num_masks) : (i += 1) {
if (self.masks[i] != other.masks[i]) {
break false;
}
} else true;
}
/// Returns true iff the first bit set is the subset
/// of the second one.
pub fn subsetOf(self: Self, other: Self) bool {
return self.intersectWith(other).eql(self);
}
/// Returns true iff the first bit set is the superset
/// of the second one.
pub fn supersetOf(self: Self, other: Self) bool {
return other.subsetOf(self);
}
/// Returns the complement bit sets. Bits in the result
/// are set if the corresponding bits were not set.
pub fn complement(self: Self) Self {
var result = self;
result.toggleAll();
return result;
}
/// Returns the union of two bit sets. Bits in the
/// result are set if the corresponding bits were set
/// in either input.
pub fn unionWith(self: Self, other: Self) Self {
var result = self;
result.setUnion(other);
return result;
}
/// Returns the intersection of two bit sets. Bits in
/// the result are set if the corresponding bits were
/// set in both inputs.
pub fn intersectWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other);
return result;
}
/// Returns the xor of two bit sets. Bits in the
/// result are set if the corresponding bits were
/// not the same in both inputs.
pub fn xorWith(self: Self, other: Self) Self {
var result = self;
result.toggleSet(other);
return result;
}
/// Returns the difference of two bit sets. Bits in
/// the result are set if set in the first but not
/// set in the second set.
pub fn differenceWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other.complement());
return result;
}
/// Iterates through the items in the set, according to the options.
/// The default options (.{}) will iterate indices of set bits in
/// ascending order. Modifications to the underlying bit set may
/// or may not be observed by the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
return Iterator(options).init(&self.masks, last_item_mask);
}
pub fn Iterator(comptime options: IteratorOptions) type {
return GenericIterator(MaskInt, options);
}
fn maskBit(index: usize) MaskInt {
return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index));
}
fn maskIndex(index: usize) usize {
return index >> @bitSizeOf(ShiftInt);
}
fn boolMaskBit(index: usize, value: bool) MaskInt {
return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
}
};
}
/// Deprecated: use `Dynamic`.
pub const DynamicBitSetUnmanaged = Dynamic;
/// A bit set with runtime-known size, backed by an allocated slice
/// of usize. The allocator must be tracked externally by the user.
pub const Dynamic = struct {
const Self = @This();
/// The integer type used to represent a mask in this bit set
pub const MaskInt = usize;
/// The integer type used to shift a mask in this bit set
pub const ShiftInt = std.math.Log2Int(MaskInt);
/// The number of valid items in this bit set
bit_length: usize = 0,
/// The bit masks, ordered with lower indices first.
/// Padding bits at the end must be zeroed.
masks: [*]MaskInt = empty_masks_ptr,
// This pointer is one usize after the actual allocation.
// That slot holds the size of the true allocation, which
// is needed by Zig's allocator interface in case a shrink
// fails.
const empty_masks_data = [_]MaskInt{ 0, undefined };
const empty_masks_ptr = @constCast(empty_masks_data[1..2]);
/// Creates a bit set with no elements present.
/// If bit_length is not zero, deinit must eventually be called.
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
var self = Self{};
try self.resize(allocator, bit_length, false);
return self;
}
/// Creates a bit set with all elements present.
/// If bit_length is not zero, deinit must eventually be called.
pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
var self = Self{};
try self.resize(allocator, bit_length, true);
return self;
}
/// Resizes to a new bit_length. If the new length is larger
/// than the old length, fills any added bits with `fill`.
/// If new_len is not zero, deinit must eventually be called.
pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void {
const old_len = self.bit_length;
const old_masks = numMasks(old_len);
const new_masks = numMasks(new_len);
const old_allocation = (self.masks - 1)[0..(self.masks - 1)[0]];
if (new_masks == 0) {
assert(new_len == 0);
allocator.free(old_allocation);
self.masks = empty_masks_ptr;
self.bit_length = 0;
return;
}
if (old_allocation.len != new_masks + 1) realloc: {
// If realloc fails, it may mean one of two things.
// If we are growing, it means we are out of memory.
// If we are shrinking, it means the allocator doesn't
// want to move the allocation. This means we need to
// hold on to the extra 8 bytes required to be able to free
// this allocation properly.
const new_allocation = allocator.realloc(old_allocation, new_masks + 1) catch |err| {
if (new_masks + 1 > old_allocation.len) return err;
break :realloc;
};
new_allocation[0] = new_allocation.len;
self.masks = new_allocation.ptr + 1;
}
// If we increased in size, we need to set any new bits
// to the fill value.
if (new_len > old_len) {
// set the padding bits in the old last item to 1
if (fill and old_masks > 0) {
const old_padding_bits = old_masks * @bitSizeOf(MaskInt) - old_len;
const old_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(old_padding_bits));
self.masks[old_masks - 1] |= ~old_mask;
}
// fill in any new masks
if (new_masks > old_masks) {
const fill_value = std.math.boolMask(MaskInt, fill);
@memset(self.masks[old_masks..new_masks], fill_value);
}
}
// Zero out the padding bits
if (new_len > 0) {
const padding_bits = new_masks * @bitSizeOf(MaskInt) - new_len;
const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
self.masks[new_masks - 1] &= last_item_mask;
}
// And finally, save the new length.
self.bit_length = new_len;
}
/// Deinitializes the array and releases its memory.
/// The passed allocator must be the same one used for
/// init* or resize in the past.
pub fn deinit(self: *Self, allocator: Allocator) void {
self.resize(allocator, 0, false) catch unreachable;
}
/// Creates a duplicate of this bit set, using the new allocator.
pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
const num_masks = numMasks(self.bit_length);
var copy = Self{};
try copy.resize(new_allocator, self.bit_length, false);
@memcpy(copy.masks[0..num_masks], self.masks[0..num_masks]);
return copy;
}
/// Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize {
return self.bit_length;
}
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
assert(index < self.bit_length);
return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
}
/// Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize {
const num_masks = (self.bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
var total: usize = 0;
for (self.masks[0..num_masks]) |mask| {
// Note: This is where we depend on padding bits being zero
total += @popCount(mask);
}
return total;
}
/// Changes the value of the specified bit of the bit
/// set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void {
assert(index < self.bit_length);
const bit = maskBit(index);
const mask_index = maskIndex(index);
const new_bit = bit & std.math.boolMask(MaskInt, value);
self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
}
/// Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void {
assert(index < self.bit_length);
self.masks[maskIndex(index)] |= maskBit(index);
}
/// Changes the value of all bits in the specified range to
/// match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
assert(range.end <= self.bit_length);
assert(range.start <= range.end);
if (range.start == range.end) return;
const start_mask_index = maskIndex(range.start);
const start_bit = @as(ShiftInt, @truncate(range.start));
const end_mask_index = maskIndex(range.end);
const end_bit = @as(ShiftInt, @truncate(range.end));
if (start_mask_index == end_mask_index) {
var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
var mask2 = std.math.boolMask(MaskInt, true) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
self.masks[start_mask_index] &= ~(mask1 & mask2);
mask1 = std.math.boolMask(MaskInt, value) << start_bit;
mask2 = std.math.boolMask(MaskInt, value) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
self.masks[start_mask_index] |= mask1 & mask2;
} else {
var bulk_mask_index: usize = undefined;
if (start_bit > 0) {
self.masks[start_mask_index] =
(self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
(std.math.boolMask(MaskInt, value) << start_bit);
bulk_mask_index = start_mask_index + 1;
} else {
bulk_mask_index = start_mask_index;
}
while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
}
if (end_bit > 0) {
self.masks[end_mask_index] =
(self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
(std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
}
}
}
/// Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void {
assert(index < self.bit_length);
self.masks[maskIndex(index)] &= ~maskBit(index);
}
/// Set all bits to 0.
pub fn unsetAll(self: *Self) void {
const masks_len = numMasks(self.bit_length);
@memset(self.masks[0..masks_len], 0);
}
/// Set all bits to 1.
pub fn setAll(self: *Self) void {
const num_masks = numMasks(self.bit_length);
@memset(self.masks[0..num_masks], std.math.maxInt(MaskInt));
if (num_masks > 0) {
const padding_bits = num_masks * @bitSizeOf(MaskInt) - self.bit_length;
const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
self.masks[num_masks - 1] = last_item_mask;
}
}
/// Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void {
assert(index < self.bit_length);
self.masks[maskIndex(index)] ^= maskBit(index);
}
/// Flips all bits in this bit set which are present
/// in the toggles bit set. Both sets must have the
/// same bit_length.
pub fn toggleSet(self: *Self, toggles: Self) void {
assert(toggles.bit_length == self.bit_length);
const num_masks = numMasks(self.bit_length);
for (self.masks[0..num_masks], 0..) |*mask, i| {
mask.* ^= toggles.masks[i];
}
}
/// Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void {
const bit_length = self.bit_length;
// avoid underflow if bit_length is zero
if (bit_length == 0) return;
const num_masks = numMasks(self.bit_length);
for (self.masks[0..num_masks]) |*mask| {
mask.* = ~mask.*;
}
const padding_bits = num_masks * @bitSizeOf(MaskInt) - bit_length;
const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
self.masks[num_masks - 1] &= last_item_mask;
}
/// Performs a union of two bit sets, and stores the
/// result in the first one. Bits in the result are
/// set if the corresponding bits were set in either input.
/// The two sets must both be the same bit_length.
pub fn setUnion(self: *Self, other: Self) void {
assert(other.bit_length == self.bit_length);
const num_masks = numMasks(self.bit_length);
for (self.masks[0..num_masks], 0..) |*mask, i| {
mask.* |= other.masks[i];
}
}
/// Performs an intersection of two bit sets, and stores
/// the result in the first one. Bits in the result are
/// set if the corresponding bits were set in both inputs.
/// The two sets must both be the same bit_length.
pub fn setIntersection(self: *Self, other: Self) void {
assert(other.bit_length == self.bit_length);
const num_masks = numMasks(self.bit_length);
for (self.masks[0..num_masks], 0..) |*mask, i| {
mask.* &= other.masks[i];
}
}
/// Finds the index of the first set bit.
/// If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize {
var offset: usize = 0;
var mask = self.masks;
while (offset < self.bit_length) {
if (mask[0] != 0) break;
mask += 1;
offset += @bitSizeOf(MaskInt);
} else return null;
return offset + @ctz(mask[0]);
}
/// Finds the index of the last set bit.
/// If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize {
if (self.bit_length == 0) return null;
const bs = @bitSizeOf(MaskInt);
var len = self.bit_length / bs;
if (self.bit_length % bs != 0) len += 1;
var offset: usize = len * bs;
var idx: usize = len - 1;
while (self.masks[idx] == 0) : (idx -= 1) {
offset -= bs;
if (idx == 0) return null;
}
offset -= @clz(self.masks[idx]);
offset -= 1;
return offset;
}
/// Finds the index of the first set bit, and unsets it.
/// If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize {
var offset: usize = 0;
var mask = self.masks;
while (offset < self.bit_length) {
if (mask[0] != 0) break;
mask += 1;
offset += @bitSizeOf(MaskInt);
} else return null;
const index = @ctz(mask[0]);
mask[0] &= (mask[0] - 1);
return offset + index;
}
/// Returns true iff every corresponding bit in both
/// bit sets are the same.
pub fn eql(self: Self, other: Self) bool {
if (self.bit_length != other.bit_length) {
return false;
}
const num_masks = numMasks(self.bit_length);
var i: usize = 0;
return while (i < num_masks) : (i += 1) {
if (self.masks[i] != other.masks[i]) {
break false;
}
} else true;
}
/// Returns true iff the first bit set is the subset
/// of the second one.
pub fn subsetOf(self: Self, other: Self) bool {
if (self.bit_length != other.bit_length) {
return false;
}
const num_masks = numMasks(self.bit_length);
var i: usize = 0;
return while (i < num_masks) : (i += 1) {
if (self.masks[i] & other.masks[i] != self.masks[i]) {
break false;
}
} else true;
}
/// Returns true iff the first bit set is the superset
/// of the second one.
pub fn supersetOf(self: Self, other: Self) bool {
if (self.bit_length != other.bit_length) {
return false;
}
const num_masks = numMasks(self.bit_length);
var i: usize = 0;
return while (i < num_masks) : (i += 1) {
if (self.masks[i] & other.masks[i] != other.masks[i]) {
break false;
}
} else true;
}
/// Iterates through the items in the set, according to the options.
/// The default options (.{}) will iterate indices of set bits in
/// ascending order. Modifications to the underlying bit set may
/// or may not be observed by the iterator. Resizing the underlying
/// bit set invalidates the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
const num_masks = numMasks(self.bit_length);
const padding_bits = num_masks * @bitSizeOf(MaskInt) - self.bit_length;
const last_item_mask = (~@as(MaskInt, 0)) >> @as(ShiftInt, @intCast(padding_bits));
return Iterator(options).init(self.masks[0..num_masks], last_item_mask);
}
pub fn Iterator(comptime options: IteratorOptions) type {
return GenericIterator(MaskInt, options);
}
fn maskBit(index: usize) MaskInt {
return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index));
}
fn maskIndex(index: usize) usize {
return index >> @bitSizeOf(ShiftInt);
}
fn boolMaskBit(index: usize, value: bool) MaskInt {
return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
}
fn numMasks(bit_length: usize) usize {
return (bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
}
};
/// Deprecated: use `DynamicManaged` or `Dynamic` (will need to update callsites).
pub const DynamicBitSet = DynamicManaged;
/// A bit set with runtime-known size, backed by an allocated slice
/// of usize. Thin wrapper around Dynamic which keeps
/// track of the allocator instance.
///
/// Deprecated in favor of `Dynamic` which accepts an `Allocator`
/// as a parameter when needed instead of storing it.
pub const DynamicManaged = struct {
const Self = @This();
/// The integer type used to represent a mask in this bit set
pub const MaskInt = usize;
/// The integer type used to shift a mask in this bit set
pub const ShiftInt = std.math.Log2Int(MaskInt);
allocator: Allocator,
unmanaged: Dynamic = .{},
/// Creates a bit set with no elements present.
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
return Self{
.unmanaged = try .initEmpty(allocator, bit_length),
.allocator = allocator,
};
}
/// Creates a bit set with all elements present.
pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
return Self{
.unmanaged = try .initFull(allocator, bit_length),
.allocator = allocator,
};
}
/// Resizes to a new length. If the new length is larger
/// than the old length, fills any added bits with `fill`.
pub fn resize(self: *@This(), new_len: usize, fill: bool) !void {
try self.unmanaged.resize(self.allocator, new_len, fill);
}
/// Deinitializes the array and releases its memory.
/// The passed allocator must be the same one used for
/// init* or resize in the past.
pub fn deinit(self: *Self) void {
self.unmanaged.deinit(self.allocator);
}
/// Creates a duplicate of this bit set, using the new allocator.
pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
return Self{
.unmanaged = try self.unmanaged.clone(new_allocator),
.allocator = new_allocator,
};
}
/// Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize {
return self.unmanaged.capacity();
}
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
return self.unmanaged.isSet(index);
}
/// Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize {
return self.unmanaged.count();
}
/// Changes the value of the specified bit of the bit
/// set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void {
self.unmanaged.setValue(index, value);
}
/// Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void {
self.unmanaged.set(index);
}
/// Changes the value of all bits in the specified range to
/// match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
self.unmanaged.setRangeValue(range, value);
}
/// Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void {
self.unmanaged.unset(index);
}
/// Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void {
self.unmanaged.toggle(index);
}
/// Flips all bits in this bit set which are present
/// in the toggles bit set. Both sets must have the
/// same bit_length.
pub fn toggleSet(self: *Self, toggles: Self) void {
self.unmanaged.toggleSet(toggles.unmanaged);
}
/// Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void {
self.unmanaged.toggleAll();
}
/// Performs a union of two bit sets, and stores the
/// result in the first one. Bits in the result are
/// set if the corresponding bits were set in either input.
/// The two sets must both be the same bit_length.
pub fn setUnion(self: *Self, other: Self) void {
self.unmanaged.setUnion(other.unmanaged);
}
/// Performs an intersection of two bit sets, and stores
/// the result in the first one. Bits in the result are
/// set if the corresponding bits were set in both inputs.
/// The two sets must both be the same bit_length.
pub fn setIntersection(self: *Self, other: Self) void {
self.unmanaged.setIntersection(other.unmanaged);
}
/// Set all bits to 0.
pub fn unsetAll(self: *Self) void {
self.unmanaged.unsetAll();
}
/// Set all bits to 1.
pub fn setAll(self: *Self) void {
self.unmanaged.setAll();
}
/// Finds the index of the first set bit.
/// If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize {
return self.unmanaged.findFirstSet();
}
/// Finds the index of the last set bit.
/// If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize {
return self.unmanaged.findLastSet();
}
/// Finds the index of the first set bit, and unsets it.
/// If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize {
return self.unmanaged.toggleFirstSet();
}
/// Returns true iff every corresponding bit in both
/// bit sets are the same.
pub fn eql(self: Self, other: Self) bool {
return self.unmanaged.eql(other.unmanaged);
}
/// Iterates through the items in the set, according to the options.
/// The default options (.{}) will iterate indices of set bits in
/// ascending order. Modifications to the underlying bit set may
/// or may not be observed by the iterator. Resizing the underlying
/// bit set invalidates the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
return self.unmanaged.iterator(options);
}
pub const Iterator = Dynamic.Iterator;
};
/// Options for configuring an iterator over a bit set
pub const IteratorOptions = struct {
/// determines which bits should be visited
kind: Type = .set,
/// determines the order in which bit indices should be visited
direction: Direction = .forward,
pub const Type = enum {
/// visit indexes of set bits
set,
/// visit indexes of unset bits
unset,
};
pub const Direction = enum {
/// visit indices in ascending order
forward,
/// visit indices in descending order.
/// Note that this may be slightly more expensive than forward iteration.
reverse,
};
};
// The iterator is reusable between several bit set types
fn GenericIterator(comptime MaskInt: type, comptime options: IteratorOptions) type {
const ShiftInt = std.math.Log2Int(MaskInt);
const kind = options.kind;
const direction = options.direction;
return struct {
const Self = @This();
// all bits which have not yet been iterated over
bits_remain: MaskInt,
// all words which have not yet been iterated over
words_remain: []const MaskInt,
// the offset of the current word
bit_offset: usize,
// the mask of the last word
last_word_mask: MaskInt,
fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self {
if (masks.len == 0) {
return Self{
.bits_remain = 0,
.words_remain = &[_]MaskInt{},
.last_word_mask = last_word_mask,
.bit_offset = 0,
};
} else {
var result = Self{
.bits_remain = 0,
.words_remain = masks,
.last_word_mask = last_word_mask,
.bit_offset = if (direction == .forward) 0 else (masks.len - 1) * @bitSizeOf(MaskInt),
};
result.nextWord(true);
return result;
}
}
/// Returns the index of the next unvisited set bit
/// in the bit set, in ascending order.
pub fn next(self: *Self) ?usize {
while (self.bits_remain == 0) {
if (self.words_remain.len == 0) return null;
self.nextWord(false);
switch (direction) {
.forward => self.bit_offset += @bitSizeOf(MaskInt),
.reverse => self.bit_offset -= @bitSizeOf(MaskInt),
}
}
switch (direction) {
.forward => {
const next_index = @ctz(self.bits_remain) + self.bit_offset;
self.bits_remain &= self.bits_remain - 1;
return next_index;
},
.reverse => {
const leading_zeroes = @clz(self.bits_remain);
const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
const no_top_bit_mask = (@as(MaskInt, 1) << @as(ShiftInt, @intCast(top_bit))) - 1;
self.bits_remain &= no_top_bit_mask;
return top_bit + self.bit_offset;
},
}
}
// Load the next word. Don't call this if there
// isn't a next word. If the next word is the
// last word, mask off the padding bits so we
// don't visit them.
inline fn nextWord(self: *Self, comptime is_first_word: bool) void {
var word = switch (direction) {
.forward => self.words_remain[0],
.reverse => self.words_remain[self.words_remain.len - 1],
};
switch (kind) {
.set => {},
.unset => {
word = ~word;
if ((direction == .reverse and is_first_word) or
(direction == .forward and self.words_remain.len == 1))
{
word &= self.last_word_mask;
}
},
}
switch (direction) {
.forward => self.words_remain = self.words_remain[1..],
.reverse => self.words_remain.len -= 1,
}
self.bits_remain = word;
}
};
}
/// A range of indices within a bitset.
pub const Range = struct {
/// The index of the first bit of interest.
start: usize,
/// The index immediately after the last bit of interest.
end: usize,
};
// ---------------- Tests -----------------
const testing = std.testing;
fn testEql(empty: anytype, full: anytype, len: usize) !void {
try testing.expect(empty.eql(empty));
try testing.expect(full.eql(full));
switch (len) {
0 => {
try testing.expect(empty.eql(full));
try testing.expect(full.eql(empty));
},
else => {
try testing.expect(!empty.eql(full));
try testing.expect(!full.eql(empty));
},
}
}
fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
try testing.expect(empty.subsetOf(empty));
try testing.expect(empty.subsetOf(full));
try testing.expect(full.subsetOf(full));
switch (len) {
0 => {
try testing.expect(even.subsetOf(odd));
try testing.expect(odd.subsetOf(even));
},
1 => {
try testing.expect(!even.subsetOf(odd));
try testing.expect(odd.subsetOf(even));
},
else => {
try testing.expect(!even.subsetOf(odd));
try testing.expect(!odd.subsetOf(even));
},
}
}
fn testSupersetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
try testing.expect(full.supersetOf(full));
try testing.expect(full.supersetOf(empty));
try testing.expect(empty.supersetOf(empty));
switch (len) {
0 => {
try testing.expect(even.supersetOf(odd));
try testing.expect(odd.supersetOf(even));
},
1 => {
try testing.expect(even.supersetOf(odd));
try testing.expect(!odd.supersetOf(even));
},
else => {
try testing.expect(!even.supersetOf(odd));
try testing.expect(!odd.supersetOf(even));
},
}
}
fn testBitSet(a: anytype, b: anytype, len: usize) !void {
try testing.expectEqual(len, a.capacity());
try testing.expectEqual(len, b.capacity());
{
var i: usize = 0;
while (i < len) : (i += 1) {
a.setValue(i, i & 1 == 0);
b.setValue(i, i & 2 == 0);
}
}
try testing.expectEqual((len + 1) / 2, a.count());
try testing.expectEqual((len + 3) / 4 + (len + 2) / 4, b.count());
{
var iter = a.iterator(.{});
var i: usize = 0;
while (i < len) : (i += 2) {
try testing.expectEqual(@as(?usize, i), iter.next());
}
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
}
a.toggleAll();
{
var iter = a.iterator(.{});
var i: usize = 1;
while (i < len) : (i += 2) {
try testing.expectEqual(@as(?usize, i), iter.next());
}
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
}
{
var iter = b.iterator(.{ .kind = .unset });
var i: usize = 2;
while (i < len) : (i += 4) {
try testing.expectEqual(@as(?usize, i), iter.next());
if (i + 1 < len) {
try testing.expectEqual(@as(?usize, i + 1), iter.next());
}
}
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
}
{
var i: usize = 0;
while (i < len) : (i += 1) {
try testing.expectEqual(i & 1 != 0, a.isSet(i));
try testing.expectEqual(i & 2 == 0, b.isSet(i));
}
}
a.setUnion(b.*);
{
var i: usize = 0;
while (i < len) : (i += 1) {
try testing.expectEqual(i & 1 != 0 or i & 2 == 0, a.isSet(i));
try testing.expectEqual(i & 2 == 0, b.isSet(i));
}
i = len;
var set = a.iterator(.{ .direction = .reverse });
var unset = a.iterator(.{ .kind = .unset, .direction = .reverse });
while (i > 0) {
i -= 1;
if (i & 1 != 0 or i & 2 == 0) {
try testing.expectEqual(@as(?usize, i), set.next());
} else {
try testing.expectEqual(@as(?usize, i), unset.next());
}
}
try testing.expectEqual(@as(?usize, null), set.next());
try testing.expectEqual(@as(?usize, null), set.next());
try testing.expectEqual(@as(?usize, null), set.next());
try testing.expectEqual(@as(?usize, null), unset.next());
try testing.expectEqual(@as(?usize, null), unset.next());
try testing.expectEqual(@as(?usize, null), unset.next());
}
a.toggleSet(b.*);
{
try testing.expectEqual(len / 4, a.count());
var i: usize = 0;
while (i < len) : (i += 1) {
try testing.expectEqual(i & 1 != 0 and i & 2 != 0, a.isSet(i));
try testing.expectEqual(i & 2 == 0, b.isSet(i));
if (i & 1 == 0) {
a.set(i);
} else {
a.unset(i);
}
}
}
a.setIntersection(b.*);
{
try testing.expectEqual((len + 3) / 4, a.count());
var i: usize = 0;
while (i < len) : (i += 1) {
try testing.expectEqual(i & 1 == 0 and i & 2 == 0, a.isSet(i));
try testing.expectEqual(i & 2 == 0, b.isSet(i));
}
}
a.toggleSet(a.*);
{
var iter = a.iterator(.{});
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(usize, 0), a.count());
}
{
var iter = a.iterator(.{ .direction = .reverse });
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(?usize, null), iter.next());
try testing.expectEqual(@as(usize, 0), a.count());
}
const test_bits = [_]usize{
0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 22, 31, 32, 63, 64,
66, 95, 127, 160, 192, 1000,
};
for (test_bits) |i| {
if (i < a.capacity()) {
a.set(i);
}
}
for (test_bits) |i| {
if (i < a.capacity()) {
try testing.expectEqual(@as(?usize, i), a.findFirstSet());
try testing.expectEqual(@as(?usize, i), a.toggleFirstSet());
}
}
try testing.expectEqual(@as(?usize, null), a.findFirstSet());
try testing.expectEqual(@as(?usize, null), a.findLastSet());
try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
try testing.expectEqual(@as(?usize, null), a.findFirstSet());
try testing.expectEqual(@as(?usize, null), a.findLastSet());
try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
try testing.expectEqual(@as(usize, 0), a.count());
a.setRangeValue(.{ .start = 0, .end = len }, false);
try testing.expectEqual(@as(usize, 0), a.count());
a.setRangeValue(.{ .start = 0, .end = len }, true);
try testing.expectEqual(len, a.count());
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = 0, .end = 0 }, true);
try testing.expectEqual(@as(usize, 0), a.count());
a.setRangeValue(.{ .start = len, .end = len }, true);
try testing.expectEqual(@as(usize, 0), a.count());
if (len >= 1) {
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = 0, .end = 1 }, true);
try testing.expectEqual(@as(usize, 1), a.count());
try testing.expect(a.isSet(0));
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = 0, .end = len - 1 }, true);
try testing.expectEqual(len - 1, a.count());
try testing.expect(!a.isSet(len - 1));
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = 1, .end = len }, true);
try testing.expectEqual(@as(usize, len - 1), a.count());
try testing.expect(!a.isSet(0));
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = len - 1, .end = len }, true);
try testing.expectEqual(@as(usize, 1), a.count());
try testing.expect(a.isSet(len - 1));
if (len >= 4) {
a.setRangeValue(.{ .start = 0, .end = len }, false);
a.setRangeValue(.{ .start = 1, .end = len - 2 }, true);
try testing.expectEqual(@as(usize, len - 3), a.count());
try testing.expect(!a.isSet(0));
try testing.expect(a.isSet(1));
try testing.expect(a.isSet(len - 3));
try testing.expect(!a.isSet(len - 2));
try testing.expect(!a.isSet(len - 1));
}
}
a.unsetAll();
try testing.expectEqual(0, a.count());
fillEven(a, len);
a.setAll();
try testing.expectEqual(len, a.count());
}
fn fillEven(set: anytype, len: usize) void {
var i: usize = 0;
while (i < len) : (i += 1) {
set.setValue(i, i & 1 == 0);
}
}
fn fillOdd(set: anytype, len: usize) void {
var i: usize = 0;
while (i < len) : (i += 1) {
set.setValue(i, i & 1 == 1);
}
}
fn testPureBitSet(comptime Set: type) !void {
const empty = Set.empty;
const full = Set.full;
const even = even: {
var bit_set = Set.empty;
fillEven(&bit_set, Set.bit_length);
break :even bit_set;
};
const odd = odd: {
var bit_set = Set.empty;
fillOdd(&bit_set, Set.bit_length);
break :odd bit_set;
};
try testSubsetOf(empty, full, even, odd, Set.bit_length);
try testSupersetOf(empty, full, even, odd, Set.bit_length);
try testing.expect(empty.complement().eql(full));
try testing.expect(full.complement().eql(empty));
try testing.expect(even.complement().eql(odd));
try testing.expect(odd.complement().eql(even));
try testing.expect(empty.unionWith(empty).eql(empty));
try testing.expect(empty.unionWith(full).eql(full));
try testing.expect(full.unionWith(full).eql(full));
try testing.expect(full.unionWith(empty).eql(full));
try testing.expect(even.unionWith(odd).eql(full));
try testing.expect(odd.unionWith(even).eql(full));
try testing.expect(empty.intersectWith(empty).eql(empty));
try testing.expect(empty.intersectWith(full).eql(empty));
try testing.expect(full.intersectWith(full).eql(full));
try testing.expect(full.intersectWith(empty).eql(empty));
try testing.expect(even.intersectWith(odd).eql(empty));
try testing.expect(odd.intersectWith(even).eql(empty));
try testing.expect(empty.xorWith(empty).eql(empty));
try testing.expect(empty.xorWith(full).eql(full));
try testing.expect(full.xorWith(full).eql(empty));
try testing.expect(full.xorWith(empty).eql(full));
try testing.expect(even.xorWith(odd).eql(full));
try testing.expect(odd.xorWith(even).eql(full));
try testing.expect(empty.differenceWith(empty).eql(empty));
try testing.expect(empty.differenceWith(full).eql(empty));
try testing.expect(full.differenceWith(full).eql(empty));
try testing.expect(full.differenceWith(empty).eql(full));
try testing.expect(full.differenceWith(odd).eql(even));
try testing.expect(full.differenceWith(even).eql(odd));
}
fn testStaticBitSet(comptime Set: type) !void {
var a = Set.empty;
var b = Set.full;
try testing.expectEqual(@as(usize, 0), a.count());
try testing.expectEqual(@as(usize, Set.bit_length), b.count());
try testEql(a, b, Set.bit_length);
try testBitSet(&a, &b, Set.bit_length);
try testPureBitSet(Set);
}
test Integer {
try testStaticBitSet(Integer(0));
try testStaticBitSet(Integer(1));
try testStaticBitSet(Integer(2));
try testStaticBitSet(Integer(5));
try testStaticBitSet(Integer(8));
try testStaticBitSet(Integer(32));
try testStaticBitSet(Integer(64));
try testStaticBitSet(Integer(127));
}
test Array {
inline for (.{ 0, 1, 2, 31, 32, 33, 63, 64, 65, 254, 500, 3000 }) |size| {
try testStaticBitSet(Array(u8, size));
try testStaticBitSet(Array(u16, size));
try testStaticBitSet(Array(u32, size));
try testStaticBitSet(Array(u64, size));
try testStaticBitSet(Array(u128, size));
}
}
test Dynamic {
const allocator = std.testing.allocator;
var a: Dynamic = try .initEmpty(allocator, 300);
try testing.expectEqual(@as(usize, 0), a.count());
a.deinit(allocator);
a = try .initEmpty(allocator, 0);
defer a.deinit(allocator);
for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
const old_len = a.capacity();
var empty = try a.clone(allocator);
defer empty.deinit(allocator);
try testing.expectEqual(old_len, empty.capacity());
var i: usize = 0;
while (i < old_len) : (i += 1) {
try testing.expectEqual(a.isSet(i), empty.isSet(i));
}
a.toggleSet(a); // zero a
empty.toggleSet(empty);
try a.resize(allocator, size, true);
try empty.resize(allocator, size, false);
if (size > old_len) {
try testing.expectEqual(size - old_len, a.count());
} else {
try testing.expectEqual(@as(usize, 0), a.count());
}
try testing.expectEqual(@as(usize, 0), empty.count());
var full: Dynamic = try .initFull(allocator, size);
defer full.deinit(allocator);
try testing.expectEqual(@as(usize, size), full.count());
try testEql(empty, full, size);
{
var even: Dynamic = try .initEmpty(allocator, size);
defer even.deinit(allocator);
fillEven(&even, size);
var odd: Dynamic = try .initEmpty(allocator, size);
defer odd.deinit(allocator);
fillOdd(&odd, size);
try testSubsetOf(empty, full, even, odd, size);
try testSupersetOf(empty, full, even, odd, size);
}
try testBitSet(&a, &full, size);
}
}
test DynamicManaged {
const allocator = std.testing.allocator;
var a: DynamicManaged = try .initEmpty(allocator, 300);
try testing.expectEqual(@as(usize, 0), a.count());
a.deinit();
a = try .initEmpty(allocator, 0);
defer a.deinit();
for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
const old_len = a.capacity();
var tmp = try a.clone(allocator);
defer tmp.deinit();
try testing.expectEqual(old_len, tmp.capacity());
var i: usize = 0;
while (i < old_len) : (i += 1) {
try testing.expectEqual(a.isSet(i), tmp.isSet(i));
}
a.toggleSet(a); // zero a
tmp.toggleSet(tmp); // zero tmp
try a.resize(size, true);
try tmp.resize(size, false);
if (size > old_len) {
try testing.expectEqual(size - old_len, a.count());
} else {
try testing.expectEqual(@as(usize, 0), a.count());
}
try testing.expectEqual(@as(usize, 0), tmp.count());
var b: DynamicManaged = try .initFull(allocator, size);
defer b.deinit();
try testing.expectEqual(@as(usize, size), b.count());
try testEql(tmp, b, size);
try testBitSet(&a, &b, size);
}
}
test Static {
try testing.expectEqual(Integer(0), Static(0));
try testing.expectEqual(Integer(5), Static(5));
try testing.expectEqual(Integer(@bitSizeOf(usize)), Static(@bitSizeOf(usize)));
try testing.expectEqual(Array(usize, @bitSizeOf(usize) + 1), Static(@bitSizeOf(usize) + 1));
try testing.expectEqual(Array(usize, 500), Static(500));
}