Skip to content
Standard libraryZig 0.17.0Official documentation
Sourcestd/bit_set.zig

Source line 1

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

Source line 34

Alias of std.mem.Allocator

std.bit_set.Array

type-function

Source line 340

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]MaskInt

The bit masks, ordered with lower indices first. Padding bits at the end are undefined.

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

Source line 381

The number of items in this bit set

usize

std.bit_set.Array.boolMaskBit

function

Source line 696

fn boolMaskBit(index: usize, value: bool) MaskInt

Parameters

index: usize
value: bool

std.bit_set.Array.capacity

function

Source line 415

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

Source line 636

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

Source line 429

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

Source line 672

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

self: Self
other: Self

std.bit_set.Array.empty

constant

Source line 405

A bit set with no elements present.

Self

std.bit_set.Array.eql

function

Source line 613

Returns true iff every corresponding bit in both bit sets are the same.

pub fn eql(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Array.findFirstSet

function

Source line 571

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

Source line 582

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

Source line 408

A bit set with all elements present.

Self

std.bit_set.Array.intersectWith

function

Source line 654

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

self: Self
other: Self

std.bit_set.Array.isSet

function

Source line 422

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

Source line 682

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

Source line 686

pub fn Iterator(comptime options: IteratorOptions) type

Parameters

options: IteratorOptions

std.bit_set.Array.last_item_mask

constant

Source line 398

std.bit_set.Array.last_pad_bits

constant

Source line 394

std.bit_set.Array.mask_len

constant

Source line 390

std.bit_set.Array.maskBit

function

Source line 690

fn maskBit(index: usize) MaskInt

Parameters

index: usize

std.bit_set.Array.maskIndex

function

Source line 693

fn maskIndex(index: usize) usize

Parameters

index: usize

std.bit_set.Array.MaskInt

constant

Source line 384

The integer type used to represent a mask in this bit set

std.bit_set.Array.num_masks

constant

Source line 392

std.bit_set.Array.Self

alias

Source line 377

Alias of std.bit_set.Array

std.bit_set.Array.set

function

Source line 449

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

Source line 542

Set all bits to 1.

pub fn setAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Array.setIntersection

function

Source line 563

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

self: *Self
other: Self

std.bit_set.Array.setRangeValue

function

Source line 457

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

self: *Self
range: Range
value: bool

std.bit_set.Array.setUnion

function

Source line 554

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

self: *Self
other: Self

std.bit_set.Array.setValue

function

Source line 439

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

self: *Self
index: usize
value: bool

std.bit_set.Array.ShiftInt

type

Source line 387

The integer type used to shift a mask in this bit set

std.bit_set.Array.subsetOf

function

Source line 624

Returns true iff the first bit set is the subset of the second one.

pub fn subsetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Array.supersetOf

function

Source line 630

Returns true iff the first bit set is the superset of the second one.

pub fn supersetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Array.toggle

function

Source line 508

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

Source line 523

Flips every bit in the bit set.

pub fn toggleAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Array.toggleFirstSet

function

Source line 600

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

Source line 516

Flips all bits in this bit set which are present in the toggles bit set.

pub fn toggleSet(self: *Self, toggles: Self) void

Parameters

self: *Self
toggles: Self

std.bit_set.Array.unionWith

function

Source line 645

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

self: Self
other: Self

std.bit_set.Array.unset

function

Source line 501

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

Source line 535

Set all bits to 0.

pub fn unsetAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Array.xorWith

function

Source line 663

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

self: Self
other: Self

std.bit_set.ArrayBitSet

alias

Source line 335

Deprecated: use Array.

Alias of std.bit_set.Array

std.bit_set.assert

alias

Source line 33

Alias of std.debug.assert

std.bit_set.builtin

constant

Source line 35

std.bit_set.Dynamic

container

Source line 707

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 = 0

The number of valid items in this bit set

masks: [*]MaskInt = empty_masks_ptr

The bit masks, ordered with lower indices first. Padding bits at the end must be zeroed.

std.bit_set.Dynamic.boolMaskBit

function

Source line 1100

fn boolMaskBit(index: usize, value: bool) MaskInt

Parameters

index: usize
value: bool

std.bit_set.Dynamic.capacity

function

Source line 825

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

Source line 816

Creates a duplicate of this bit set, using the new allocator.

pub fn clone(self: *const Self, new_allocator: Allocator) !Self

Parameters

self: *const Self
new_allocator: Allocator

std.bit_set.Dynamic.count

function

Source line 837

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

Source line 811

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

self: *Self
allocator: Allocator

std.bit_set.Dynamic.empty_masks_data

constant

Source line 726

std.bit_set.Dynamic.empty_masks_ptr

constant

Source line 727

std.bit_set.Dynamic.eql

function

Source line 1035

Returns true iff every corresponding bit in both bit sets are the same.

pub fn eql(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Dynamic.findFirstSet

function

Source line 989

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

Source line 1002

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

Source line 731

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

Source line 739

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

Source line 831

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

Source line 1083

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

Source line 1090

pub fn Iterator(comptime options: IteratorOptions) type

Parameters

options: IteratorOptions

std.bit_set.Dynamic.maskBit

function

Source line 1094

fn maskBit(index: usize) MaskInt

Parameters

index: usize

std.bit_set.Dynamic.maskIndex

function

Source line 1097

fn maskIndex(index: usize) usize

Parameters

index: usize

std.bit_set.Dynamic.MaskInt

type

Source line 711

The integer type used to represent a mask in this bit set

std.bit_set.Dynamic.numMasks

function

Source line 1103

fn numMasks(bit_length: usize) usize

Parameters

bit_length: usize

std.bit_set.Dynamic.resize

function

Source line 748

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

self: *@This()
allocator: Allocator
new_len: usize
fill: bool

std.bit_set.Dynamic.Self

alias

Source line 708

Alias of std.bit_set.Dynamic

std.bit_set.Dynamic.set

function

Source line 858

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

Source line 920

Set all bits to 1.

pub fn setAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Dynamic.setIntersection

function

Source line 979

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

self: *Self
other: Self

std.bit_set.Dynamic.setRangeValue

function

Source line 865

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

self: *Self
range: Range
value: bool

std.bit_set.Dynamic.setUnion

function

Source line 967

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

self: *Self
other: Self

std.bit_set.Dynamic.setValue

function

Source line 849

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

self: *Self
index: usize
value: bool

std.bit_set.Dynamic.ShiftInt

type

Source line 714

The integer type used to shift a mask in this bit set

std.bit_set.Dynamic.subsetOf

function

Source line 1050

Returns true iff the first bit set is the subset of the second one.

pub fn subsetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Dynamic.supersetOf

function

Source line 1065

Returns true iff the first bit set is the superset of the second one.

pub fn supersetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Dynamic.toggle

function

Source line 931

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

Source line 948

Flips every bit in the bit set.

pub fn toggleAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Dynamic.toggleFirstSet

function

Source line 1020

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

Source line 939

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

self: *Self
toggles: Self

std.bit_set.Dynamic.unset

function

Source line 908

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

Source line 914

Set all bits to 0.

pub fn unsetAll(self: *Self) void

Parameters

self: *Self

std.bit_set.DynamicBitSet

alias

Source line 1109

Deprecated: use DynamicManaged or Dynamic (will need to update callsites).

Alias of std.bit_set.DynamicManaged

std.bit_set.DynamicBitSetUnmanaged

alias

Source line 703

Deprecated: use Dynamic.

Alias of std.bit_set.Dynamic

std.bit_set.DynamicManaged

container

Source line 1117

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

allocator: Allocator
unmanaged: Dynamic = .{}

std.bit_set.DynamicManaged.capacity

function

Source line 1167

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

Source line 1159

Creates a duplicate of this bit set, using the new allocator.

pub fn clone(self: *const Self, new_allocator: Allocator) !Self

Parameters

self: *const Self
new_allocator: Allocator

std.bit_set.DynamicManaged.count

function

Source line 1178

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

Source line 1154

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

Source line 1267

Returns true iff every corresponding bit in both bit sets are the same.

pub fn eql(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.DynamicManaged.findFirstSet

function

Source line 1249

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

Source line 1255

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

Source line 1130

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

Source line 1138

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

Source line 1173

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

Source line 1276

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

Source line 1280

Alias of std.bit_set.Dynamic.Iterator

std.bit_set.DynamicManaged.MaskInt

type

Source line 1121

The integer type used to represent a mask in this bit set

std.bit_set.DynamicManaged.resize

function

Source line 1147

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

Source line 1118

Alias of std.bit_set.DynamicManaged

std.bit_set.DynamicManaged.set

function

Source line 1189

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

Source line 1243

Set all bits to 1.

pub fn setAll(self: *Self) void

Parameters

self: *Self

std.bit_set.DynamicManaged.setIntersection

function

Source line 1233

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

self: *Self
other: Self

std.bit_set.DynamicManaged.setRangeValue

function

Source line 1195

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

self: *Self
range: Range
value: bool

std.bit_set.DynamicManaged.setUnion

function

Source line 1225

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

self: *Self
other: Self

std.bit_set.DynamicManaged.setValue

function

Source line 1184

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

self: *Self
index: usize
value: bool

std.bit_set.DynamicManaged.ShiftInt

type

Source line 1124

The integer type used to shift a mask in this bit set

std.bit_set.DynamicManaged.toggle

function

Source line 1205

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

Source line 1217

Flips every bit in the bit set.

pub fn toggleAll(self: *Self) void

Parameters

self: *Self

std.bit_set.DynamicManaged.toggleFirstSet

function

Source line 1261

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

Source line 1212

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

self: *Self
toggles: Self

std.bit_set.DynamicManaged.unset

function

Source line 1200

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

Source line 1238

Set all bits to 0.

pub fn unsetAll(self: *Self) void

Parameters

self: *Self

std.bit_set.fillEven

function

Source line 1674

fn fillEven(set: anytype, len: usize) void

Parameters

len: usize

std.bit_set.fillOdd

function

Source line 1681

fn fillOdd(set: anytype, len: usize) void

Parameters

len: usize

std.bit_set.GenericIterator

type-function

Source line 1307

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

Source line 1323

fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self

Parameters

masks: []const MaskInt
last_word_mask: MaskInt

std.bit_set.GenericIterator.next

function

Source line 1345

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

Source line 1375

inline fn nextWord(self: *Self, comptime is_first_word: bool) void

Parameters

self: *Self
is_first_word: bool

std.bit_set.GenericIterator.Self

alias

Source line 1312

Alias of std.bit_set.GenericIterator

std.bit_set.Integer

type-function

Source line 59

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: MaskInt

The bit mask, as a single integer

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

Source line 65

The number of items in this bit set

usize

std.bit_set.Integer.boolMaskBit

function

Source line 327

fn boolMaskBit(index: usize, value: bool) MaskInt

Parameters

index: usize
value: bool

std.bit_set.Integer.capacity

function

Source line 83

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

Source line 236

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

Source line 96

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

Source line 272

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

self: Self
other: Self

std.bit_set.Integer.empty

constant

Source line 77

A bit set with no elements present.

Self

std.bit_set.Integer.eql

function

Source line 218

Returns true iff every corresponding bit in both bit sets are the same.

pub fn eql(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Integer.findFirstSet

function

Source line 192

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

Source line 200

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

Source line 80

A bit set with all elements present.

Self

std.bit_set.Integer.intersectWith

function

Source line 254

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

self: Self
other: Self

std.bit_set.Integer.isSet

function

Source line 90

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

Source line 282

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

Source line 291

pub fn Iterator(comptime options: IteratorOptions) type

Parameters

options: IteratorOptions

std.bit_set.Integer.maskBit

function

Source line 323

fn maskBit(index: usize) MaskInt

Parameters

index: usize

std.bit_set.Integer.MaskInt

constant

Source line 68

The integer type used to represent a mask in this bit set

std.bit_set.Integer.Self

alias

Source line 61

Alias of std.bit_set.Integer

std.bit_set.Integer.set

function

Source line 111

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

Source line 172

Set all bits to 1.

pub fn setAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Integer.setIntersection

function

Source line 186

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

self: *Self
other: Self

std.bit_set.Integer.setRangeValue

function

Source line 118

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

self: *Self
range: Range
value: bool

std.bit_set.Integer.setUnion

function

Source line 179

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

self: *Self
other: Self

std.bit_set.Integer.setValue

function

Source line 102

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

self: *Self
index: usize
value: bool

std.bit_set.Integer.ShiftInt

type

Source line 71

The integer type used to shift a mask in this bit set

std.bit_set.Integer.SingleWordIterator

type-function

Source line 295

fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type

Parameters

Fields

bits_remain: MaskInt

std.bit_set.Integer.SingleWordIterator.IterSelf

alias

Source line 297

Alias of std.bit_set.Integer.SingleWordIterator

std.bit_set.Integer.SingleWordIterator.next

function

Source line 303

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

Source line 224

Returns true iff the first bit set is the subset of the second one.

pub fn subsetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Integer.supersetOf

function

Source line 230

Returns true iff the first bit set is the superset of the second one.

pub fn supersetOf(self: Self, other: Self) bool

Parameters

self: Self
other: Self

std.bit_set.Integer.toggle

function

Source line 150

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

Source line 162

Flips every bit in the bit set.

pub fn toggleAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Integer.toggleFirstSet

function

Source line 208

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

Source line 157

Flips all bits in this bit set which are present in the toggles bit set.

pub fn toggleSet(self: *Self, toggles: Self) void

Parameters

self: *Self
toggles: Self

std.bit_set.Integer.unionWith

function

Source line 245

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

self: Self
other: Self

std.bit_set.Integer.unset

function

Source line 142

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

Source line 167

Set all bits to 0.

pub fn unsetAll(self: *Self) void

Parameters

self: *Self

std.bit_set.Integer.xorWith

function

Source line 263

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

self: Self
other: Self

std.bit_set.IntegerBitSet

alias

Source line 54

Deprecated: use Integer.

Alias of std.bit_set.Integer

std.bit_set.IteratorOptions

container

Source line 1284

Options for configuring an iterator over a bit set

Fields

kind: Type = .set

determines which bits should be visited

direction: Direction = .forward

determines the order in which bit indices should be visited

std.bit_set.IteratorOptions.Direction

container

Source line 1297

Fields

forward

visit indices in ascending order

reverse

visit indices in descending order. Note that this may be slightly more expensive than forward iteration.

std.bit_set.IteratorOptions.Type

container

Source line 1290

Fields

set

visit indexes of set bits

unset

visit indexes of unset bits

std.bit_set.Range

container

Source line 1401

A range of indices within a bitset.

Fields

start: usize

The index of the first bit of interest.

end: usize

The index immediately after the last bit of interest.

std.bit_set.Static

type-function

Source line 45

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

Source line 38

Deprecated: use Static.

Alias of std.bit_set.Static

std.bit_set.std

alias

Source line 32

Alias of std

std.bit_set.testBitSet

function

Source line 1467

fn testBitSet(a: anytype, b: anytype, len: usize) !void

Parameters

len: usize

std.bit_set.testEql

function

Source line 1412

fn testEql(empty: anytype, full: anytype, len: usize) !void

Parameters

len: usize

std.bit_set.testing

alias

Source line 1410

Alias of std.testing

std.bit_set.testPureBitSet

function

Source line 1688

fn testPureBitSet(comptime Set: type) !void

Parameters

Set: type

std.bit_set.testStaticBitSet

function

Source line 1741

fn testStaticBitSet(comptime Set: type) !void

Parameters

Set: type

std.bit_set.testSubsetOf

function

Source line 1427

fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void

Parameters

len: usize

std.bit_set.testSupersetOf

function

Source line 1447

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));
}