跳转到内容
标准库Zig 0.17.0官方原文
源码std/bit_set.zig

第 1 行

此文件定义了几种位集合。位集合是对整数集合的密集存储形式,集合的最大值已知,且每个整数对应一个位。位集合的存在性检查、更新、并集和交集运算都非常快。不过,如果可能的元素数量非常大,而给定集合中的实际元素通常很少,那么它们的内存效率可能低于数组集合。

此处定义了五种变体:

Integer: 静态大小的位集合,由单个整数作为后备存储。 适用于元素较少的集合;但集合较大时,尤其在调试模式下,可能生成效率较低的代码。

Array: 静态大小的位集合,由 usize 数组作为后备存储。 适用于元素较多的集合;但集合较小时,可能占用多余字节。

Static: 根据请求的大小选择 Integer 或 Array。 除字段外,这两种类型的接口完全一致。

Dynamic: 大小在运行期才确定的位集合,由已分配的 usize 切片作为后备存储。

DynamicManaged: Dynamic 的一种变体,会存储分配器,并在需要时使用它。

std.bit_set.Allocator

别名

第 34 行

别名目标 std.mem.Allocator

std.bit_set.Array

类型函数

第 340 行

静态大小的位集合,由 usize 数组作为底层存储。 适合较大的集合;但集合较小时, 占用的字节数可能多于必要值。

pub fn Array(comptime MaskIntType: type, comptime size: usize) type

参数

MaskIntType: type
size: usize

字段

masks: [num_masks]MaskInt

按低索引在前的顺序排列位掩码。末尾的填充位未定义。

用法示例

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

常量

第 381 行

此位集中的条目数量

usize

std.bit_set.Array.boolMaskBit

函数

第 696 行

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

参数

index: usize
value: bool

std.bit_set.Array.capacity

函数

第 415 行

返回此位集合中的位数

pub inline fn capacity(self: Self) usize

参数

self: Self

std.bit_set.Array.complement

函数

第 636 行

返回位集合的补集。若对应位原先未设置, 则结果中的该位会被设置。

pub fn complement(self: Self) Self

参数

self: Self

std.bit_set.Array.count

函数

第 429 行

返回此位集合中已设置位的总数。

pub fn count(self: Self) usize

参数

self: Self

std.bit_set.Array.differenceWith

函数

第 672 行

返回两个位集合的差集。 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。

pub fn differenceWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Array.empty

常量

第 405 行

不含任何元素的位集合。

Self

std.bit_set.Array.eql

函数

第 613 行

当且仅当两个位集合中的每一对 对应位都相同时,返回 true。

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

参数

self: Self
other: Self

std.bit_set.Array.findFirstSet

函数

第 571 行

查找首个置位的索引。 若没有置位,则返回 null。

pub fn findFirstSet(self: Self) ?usize

参数

self: Self

std.bit_set.Array.findLastSet

函数

第 582 行

查找最后一个置位的索引。 若没有置位,则返回 null。

pub fn findLastSet(self: Self) ?usize

参数

self: Self

std.bit_set.Array.full

常量

第 408 行

包含所有元素的位集。

Self

std.bit_set.Array.intersectWith

函数

第 654 行

返回两个位集合的交集。 只有两个输入中的对应位都已置位,结果中的该位才置位。

pub fn intersectWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Array.isSet

函数

第 422 行

指定索引处的位存在于集合中时返回 true, 否则返回 false。

pub fn isSet(self: Self, index: usize) bool

参数

self: Self
index: usize

std.bit_set.Array.iterator

函数

第 682 行

根据选项遍历集合中的元素。 默认选项(.{})会按升序遍历 已置位的位索引。对底层位集合的修改 可能被迭代器观察到,也可能不会。

pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)

参数

self: *const Self
options: IteratorOptions

std.bit_set.Array.Iterator

类型函数

第 686 行

pub fn Iterator(comptime options: IteratorOptions) type

参数

options: IteratorOptions

std.bit_set.Array.last_item_mask

常量

第 398 行

std.bit_set.Array.last_pad_bits

常量

第 394 行

std.bit_set.Array.mask_len

常量

第 390 行

std.bit_set.Array.maskBit

函数

第 690 行

fn maskBit(index: usize) MaskInt

参数

index: usize

std.bit_set.Array.maskIndex

函数

第 693 行

fn maskIndex(index: usize) usize

参数

index: usize

std.bit_set.Array.MaskInt

常量

第 384 行

在此位集合中用于表示掩码的整数类型

std.bit_set.Array.num_masks

常量

第 392 行

std.bit_set.Array.Self

别名

第 377 行

别名目标 std.bit_set.Array

std.bit_set.Array.set

函数

第 449 行

向位集合添加指定位

pub fn set(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Array.setAll

函数

第 542 行

将所有位设为 1。

pub fn setAll(self: *Self) void

参数

self: *Self

std.bit_set.Array.setIntersection

函数

第 563 行

对两个位集执行交集,并将 结果存入第一个位集。仅当两个输入的对应位 均置位时,结果中的对应位才置位。

pub fn setIntersection(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Array.setRangeValue

函数

第 457 行

将指定范围内所有位的值改为 给定布尔值。

pub fn setRangeValue(self: *Self, range: Range, value: bool) void

参数

self: *Self
range: Range
value: bool

std.bit_set.Array.setUnion

函数

第 554 行

对两个位集合求并集,并将结果存储在第一个集合中。 若任一输入中的对应位已置位,则结果中的该位置位。

pub fn setUnion(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Array.setValue

函数

第 439 行

将位集合中指定的位 设置为与传入布尔值一致。

pub fn setValue(self: *Self, index: usize, value: bool) void

参数

self: *Self
index: usize
value: bool

std.bit_set.Array.ShiftInt

类型

第 387 行

用于对此位集合中的掩码移位的整数类型。

std.bit_set.Array.subsetOf

函数

第 624 行

当且仅当第一个位集合是第二个的子集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Array.supersetOf

函数

第 630 行

当且仅当第一个位集合为第二个位集合的 超集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Array.toggle

函数

第 508 行

翻转位集合中的指定位

pub fn toggle(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Array.toggleAll

函数

第 523 行

翻转位集合中的每一位。

pub fn toggleAll(self: *Self) void

参数

self: *Self

std.bit_set.Array.toggleFirstSet

函数

第 600 行

查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。

pub fn toggleFirstSet(self: *Self) ?usize

参数

self: *Self

std.bit_set.Array.toggleSet

函数

第 516 行

翻转此位集合中所有也存在于 toggles 位集合的位。

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

参数

self: *Self
toggles: Self

std.bit_set.Array.unionWith

函数

第 645 行

返回两个位集合的并集。 任一输入的对应位置位时, 结果的该位置位。

pub fn unionWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Array.unset

函数

第 501 行

从位集合中移除指定的位

pub fn unset(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Array.unsetAll

函数

第 535 行

将所有位设为 0。

pub fn unsetAll(self: *Self) void

参数

self: *Self

std.bit_set.Array.xorWith

函数

第 663 行

返回两个位集合的异或。 若两个输入的对应位不同, 结果中该位置位。

pub fn xorWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.ArrayBitSet

别名

第 335 行

已弃用:使用 Array。

别名目标 std.bit_set.Array

std.bit_set.assert

别名

第 33 行

别名目标 std.debug.assert

std.bit_set.builtin

常量

第 35 行

std.bit_set.Dynamic

容器

第 707 行

大小在运行期已知、由已分配 usize 切片提供存储的位集合。 分配器必须由用户在外部跟踪。

字段

bit_length: usize = 0

此位集合中有效项的数量

masks: [*]MaskInt = empty_masks_ptr

按低索引在前的顺序排列位掩码。 末尾的填充位必须清零。

std.bit_set.Dynamic.boolMaskBit

函数

第 1100 行

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

参数

index: usize
value: bool

std.bit_set.Dynamic.capacity

函数

第 825 行

返回此位集合中的位数

pub inline fn capacity(self: Self) usize

参数

self: Self

std.bit_set.Dynamic.clone

函数

第 816 行

使用新分配器创建此位集合的副本。

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

参数

self: *const Self
new_allocator: Allocator

std.bit_set.Dynamic.count

函数

第 837 行

返回此位集合中已设置位的总数。

pub fn count(self: Self) usize

参数

self: Self

std.bit_set.Dynamic.deinit

函数

第 811 行

反初始化数组并释放其内存。 传入的分配器必须与此前用于 init* 或 resize 的分配器相同。

pub fn deinit(self: *Self, allocator: Allocator) void

参数

self: *Self
allocator: Allocator

std.bit_set.Dynamic.empty_masks_data

常量

第 726 行

std.bit_set.Dynamic.empty_masks_ptr

常量

第 727 行

std.bit_set.Dynamic.eql

函数

第 1035 行

当且仅当两个位集合中的每一对 对应位都相同时,返回 true。

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

参数

self: Self
other: Self

std.bit_set.Dynamic.findFirstSet

函数

第 989 行

查找首个置位的索引。 若没有置位,则返回 null。

pub fn findFirstSet(self: Self) ?usize

参数

self: Self

std.bit_set.Dynamic.findLastSet

函数

第 1002 行

查找最后一个置位的索引。 若没有置位,则返回 null。

pub fn findLastSet(self: Self) ?usize

参数

self: Self

std.bit_set.Dynamic.initEmpty

函数

第 731 行

创建不含任何元素的位集合。 如果 bit_length 非零,最终必须调用 deinit。

pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self

参数

allocator: Allocator
bit_length: usize

std.bit_set.Dynamic.initFull

函数

第 739 行

创建包含所有元素的位集合。 若 bit_length 非零,最终必须调用 deinit。

pub fn initFull(allocator: Allocator, bit_length: usize) !Self

参数

allocator: Allocator
bit_length: usize

std.bit_set.Dynamic.isSet

函数

第 831 行

指定索引处的位存在于集合中时返回 true, 否则返回 false。

pub fn isSet(self: Self, index: usize) bool

参数

self: Self
index: usize

std.bit_set.Dynamic.iterator

函数

第 1083 行

按选项遍历集合中的元素。 默认选项 .{} 按升序遍历已设置位的索引。 迭代器可能观察到对底层位集的修改,也可能观察不到。 调整底层位集大小会使迭代器失效。

pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)

参数

self: *const Self
options: IteratorOptions

std.bit_set.Dynamic.Iterator

类型函数

第 1090 行

pub fn Iterator(comptime options: IteratorOptions) type

参数

options: IteratorOptions

std.bit_set.Dynamic.maskBit

函数

第 1094 行

fn maskBit(index: usize) MaskInt

参数

index: usize

std.bit_set.Dynamic.maskIndex

函数

第 1097 行

fn maskIndex(index: usize) usize

参数

index: usize

std.bit_set.Dynamic.MaskInt

类型

第 711 行

在此位集合中用于表示掩码的整数类型

std.bit_set.Dynamic.numMasks

函数

第 1103 行

fn numMasks(bit_length: usize) usize

参数

bit_length: usize

std.bit_set.Dynamic.resize

函数

第 748 行

调整为新的 bit_length。若新长度大于 旧长度,则使用 fill 填充新增位。 若 new_len 非零,最终必须调用 deinit。

pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void

参数

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

std.bit_set.Dynamic.Self

别名

第 708 行

别名目标 std.bit_set.Dynamic

std.bit_set.Dynamic.set

函数

第 858 行

向位集合添加指定位

pub fn set(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Dynamic.setAll

函数

第 920 行

将所有位设为 1。

pub fn setAll(self: *Self) void

参数

self: *Self

std.bit_set.Dynamic.setIntersection

函数

第 979 行

计算两个位集合的交集,并将结果 存入第一个集合。仅当两个输入中的对应位 均已置位时,结果中的该位才置位。 两个集合的 bit_length 必须相同。

pub fn setIntersection(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Dynamic.setRangeValue

函数

第 865 行

将指定范围内所有位的值改为 给定布尔值。

pub fn setRangeValue(self: *Self, range: Range, value: bool) void

参数

self: *Self
range: Range
value: bool

std.bit_set.Dynamic.setUnion

函数

第 967 行

对两个位集执行并集,并将 结果存入第一个位集。任一输入中的对应位置位时, 结果中的对应位即置位。 两个位集必须具有相同的 bit_length。

pub fn setUnion(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Dynamic.setValue

函数

第 849 行

将位集合中指定的位 设置为与传入布尔值一致。

pub fn setValue(self: *Self, index: usize, value: bool) void

参数

self: *Self
index: usize
value: bool

std.bit_set.Dynamic.ShiftInt

类型

第 714 行

用于对此位集合中的掩码移位的整数类型。

std.bit_set.Dynamic.subsetOf

函数

第 1050 行

当且仅当第一个位集合是第二个的子集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Dynamic.supersetOf

函数

第 1065 行

当且仅当第一个位集合为第二个位集合的 超集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Dynamic.toggle

函数

第 931 行

翻转位集合中的指定位

pub fn toggle(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Dynamic.toggleAll

函数

第 948 行

翻转位集合中的每一位。

pub fn toggleAll(self: *Self) void

参数

self: *Self

std.bit_set.Dynamic.toggleFirstSet

函数

第 1020 行

查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。

pub fn toggleFirstSet(self: *Self) ?usize

参数

self: *Self

std.bit_set.Dynamic.toggleSet

函数

第 939 行

翻转此位集合中在 toggles 位集合中出现的所有位。 两个集合必须具有相同 bit_length。

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

参数

self: *Self
toggles: Self

std.bit_set.Dynamic.unset

函数

第 908 行

从位集合中移除指定的位

pub fn unset(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Dynamic.unsetAll

函数

第 914 行

将所有位设为 0。

pub fn unsetAll(self: *Self) void

参数

self: *Self

std.bit_set.DynamicBitSet

别名

第 1109 行

已弃用:使用 DynamicManaged 或 Dynamic(需要更新调用位置)。

别名目标 std.bit_set.DynamicManaged

std.bit_set.DynamicBitSetUnmanaged

别名

第 703 行

已弃用:使用 Dynamic。

别名目标 std.bit_set.Dynamic

std.bit_set.DynamicManaged

容器

第 1117 行

大小在运行时已知的位集,以已分配的 usize 切片作为底层存储。对 Dynamic 的轻量封装, 用于跟踪分配器实例。

已弃用,请改用 Dynamic;后者在需要时接受 Allocator 参数,而不存储它。

字段

allocator: Allocator
unmanaged: Dynamic = .{}

std.bit_set.DynamicManaged.capacity

函数

第 1167 行

返回此位集合中的位数

pub inline fn capacity(self: Self) usize

参数

self: Self

std.bit_set.DynamicManaged.clone

函数

第 1159 行

使用新分配器创建此位集合的副本。

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

参数

self: *const Self
new_allocator: Allocator

std.bit_set.DynamicManaged.count

函数

第 1178 行

返回此位集合中已设置位的总数。

pub fn count(self: Self) usize

参数

self: Self

std.bit_set.DynamicManaged.deinit

函数

第 1154 行

反初始化数组并释放其内存。 传入的分配器必须与此前用于 init* 或 resize 的分配器相同。

pub fn deinit(self: *Self) void

参数

self: *Self

std.bit_set.DynamicManaged.eql

函数

第 1267 行

当且仅当两个位集合中的每一对 对应位都相同时,返回 true。

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

参数

self: Self
other: Self

std.bit_set.DynamicManaged.findFirstSet

函数

第 1249 行

查找首个置位的索引。 若没有置位,则返回 null。

pub fn findFirstSet(self: Self) ?usize

参数

self: Self

std.bit_set.DynamicManaged.findLastSet

函数

第 1255 行

查找最后一个置位的索引。 若没有置位,则返回 null。

pub fn findLastSet(self: Self) ?usize

参数

self: Self

std.bit_set.DynamicManaged.initEmpty

函数

第 1130 行

创建不含任何元素的位集。

pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self

参数

allocator: Allocator
bit_length: usize

std.bit_set.DynamicManaged.initFull

函数

第 1138 行

创建包含所有元素的位集。

pub fn initFull(allocator: Allocator, bit_length: usize) !Self

参数

allocator: Allocator
bit_length: usize

std.bit_set.DynamicManaged.isSet

函数

第 1173 行

指定索引处的位存在于集合中时返回 true, 否则返回 false。

pub fn isSet(self: Self, index: usize) bool

参数

self: Self
index: usize

std.bit_set.DynamicManaged.iterator

函数

第 1276 行

按选项遍历集合中的元素。 默认选项 .{} 按升序遍历已设置位的索引。 迭代器可能观察到对底层位集的修改,也可能观察不到。 调整底层位集大小会使迭代器失效。

pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)

参数

self: *const Self
options: IteratorOptions

std.bit_set.DynamicManaged.Iterator

别名

第 1280 行

别名目标 std.bit_set.Dynamic.Iterator

std.bit_set.DynamicManaged.MaskInt

类型

第 1121 行

在此位集合中用于表示掩码的整数类型

std.bit_set.DynamicManaged.resize

函数

第 1147 行

调整为新长度。如果新长度大于 旧长度,则用 fill 填充新增位。

pub fn resize(self: *@This(), new_len: usize, fill: bool) !void

参数

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

std.bit_set.DynamicManaged.Self

别名

第 1118 行

别名目标 std.bit_set.DynamicManaged

std.bit_set.DynamicManaged.set

函数

第 1189 行

向位集合添加指定位

pub fn set(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.DynamicManaged.setAll

函数

第 1243 行

将所有位设为 1。

pub fn setAll(self: *Self) void

参数

self: *Self

std.bit_set.DynamicManaged.setIntersection

函数

第 1233 行

计算两个位集合的交集,并将结果 存入第一个集合。仅当两个输入中的对应位 均已置位时,结果中的该位才置位。 两个集合的 bit_length 必须相同。

pub fn setIntersection(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.DynamicManaged.setRangeValue

函数

第 1195 行

将指定范围内所有位的值改为 给定布尔值。

pub fn setRangeValue(self: *Self, range: Range, value: bool) void

参数

self: *Self
range: Range
value: bool

std.bit_set.DynamicManaged.setUnion

函数

第 1225 行

对两个位集执行并集,并将 结果存入第一个位集。任一输入中的对应位置位时, 结果中的对应位即置位。 两个位集必须具有相同的 bit_length。

pub fn setUnion(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.DynamicManaged.setValue

函数

第 1184 行

将位集合中指定的位 设置为与传入布尔值一致。

pub fn setValue(self: *Self, index: usize, value: bool) void

参数

self: *Self
index: usize
value: bool

std.bit_set.DynamicManaged.ShiftInt

类型

第 1124 行

用于对此位集合中的掩码移位的整数类型。

std.bit_set.DynamicManaged.toggle

函数

第 1205 行

翻转位集合中的指定位

pub fn toggle(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.DynamicManaged.toggleAll

函数

第 1217 行

翻转位集合中的每一位。

pub fn toggleAll(self: *Self) void

参数

self: *Self

std.bit_set.DynamicManaged.toggleFirstSet

函数

第 1261 行

查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。

pub fn toggleFirstSet(self: *Self) ?usize

参数

self: *Self

std.bit_set.DynamicManaged.toggleSet

函数

第 1212 行

翻转此位集合中在 toggles 位集合中出现的所有位。 两个集合必须具有相同 bit_length。

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

参数

self: *Self
toggles: Self

std.bit_set.DynamicManaged.unset

函数

第 1200 行

从位集合中移除指定的位

pub fn unset(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.DynamicManaged.unsetAll

函数

第 1238 行

将所有位设为 0。

pub fn unsetAll(self: *Self) void

参数

self: *Self

std.bit_set.fillEven

函数

第 1674 行

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

参数

len: usize

std.bit_set.fillOdd

函数

第 1681 行

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

参数

len: usize

std.bit_set.GenericIterator

类型函数

第 1307 行

fn GenericIterator(comptime MaskInt: type, comptime options: IteratorOptions) type

参数

MaskInt: type
options: IteratorOptions

字段

bits_remain: MaskInt
words_remain: []const MaskInt
bit_offset: usize
last_word_mask: MaskInt

std.bit_set.GenericIterator.init

函数

第 1323 行

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

参数

masks: []const MaskInt
last_word_mask: MaskInt

std.bit_set.GenericIterator.next

函数

第 1345 行

按升序返回位集合中下一个尚未访问的置位索引。

pub fn next(self: *Self) ?usize

参数

self: *Self

std.bit_set.GenericIterator.nextWord

函数

第 1375 行

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

参数

self: *Self
is_first_word: bool

std.bit_set.GenericIterator.Self

别名

第 1312 行

别名目标 std.bit_set.GenericIterator

std.bit_set.Integer

类型函数

第 59 行

以单个整数作为底层存储的固定大小位集。 适合较小的集合,但对于较大的集合, 可能生成低效代码,尤其在调试模式下。

pub fn Integer(comptime size: u16) type

参数

size: u16

字段

mask: MaskInt

将位掩码表示为单个整数

用法示例

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

常量

第 65 行

此位集中的条目数量

usize

std.bit_set.Integer.boolMaskBit

函数

第 327 行

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

参数

index: usize
value: bool

std.bit_set.Integer.capacity

函数

第 83 行

返回此位集合中的位数

pub inline fn capacity(self: Self) usize

参数

self: Self

std.bit_set.Integer.complement

函数

第 236 行

返回位集合的补集。若对应位原先未设置, 则结果中的该位会被设置。

pub fn complement(self: Self) Self

参数

self: Self

std.bit_set.Integer.count

函数

第 96 行

返回此位集合中已设置位的总数。

pub fn count(self: Self) usize

参数

self: Self

std.bit_set.Integer.differenceWith

函数

第 272 行

返回两个位集合的差集。 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。

pub fn differenceWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Integer.empty

常量

第 77 行

不含任何元素的位集合。

Self

std.bit_set.Integer.eql

函数

第 218 行

当且仅当两个位集合中的每一对 对应位都相同时,返回 true。

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

参数

self: Self
other: Self

std.bit_set.Integer.findFirstSet

函数

第 192 行

查找首个置位的索引。 若没有置位,则返回 null。

pub fn findFirstSet(self: Self) ?usize

参数

self: Self

std.bit_set.Integer.findLastSet

函数

第 200 行

查找最后一个置位的索引。 若没有置位,则返回 null。

pub fn findLastSet(self: Self) ?usize

参数

self: Self

std.bit_set.Integer.full

常量

第 80 行

包含所有元素的位集。

Self

std.bit_set.Integer.intersectWith

函数

第 254 行

返回两个位集合的交集。 只有两个输入中的对应位都已置位,结果中的该位才置位。

pub fn intersectWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Integer.isSet

函数

第 90 行

指定索引处的位存在于集合中时返回 true, 否则返回 false。

pub fn isSet(self: Self, index: usize) bool

参数

self: Self
index: usize

std.bit_set.Integer.iterator

函数

第 282 行

根据选项遍历集合中的元素。 默认选项(.{})会按升序遍历 已置位的位索引。对底层位集合的修改 可能被迭代器观察到,也可能不会。

pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)

参数

self: *const Self
options: IteratorOptions

std.bit_set.Integer.Iterator

类型函数

第 291 行

pub fn Iterator(comptime options: IteratorOptions) type

参数

options: IteratorOptions

std.bit_set.Integer.maskBit

函数

第 323 行

fn maskBit(index: usize) MaskInt

参数

index: usize

std.bit_set.Integer.MaskInt

常量

第 68 行

在此位集合中用于表示掩码的整数类型

std.bit_set.Integer.Self

别名

第 61 行

别名目标 std.bit_set.Integer

std.bit_set.Integer.set

函数

第 111 行

向位集合添加指定位

pub fn set(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Integer.setAll

函数

第 172 行

将所有位设为 1。

pub fn setAll(self: *Self) void

参数

self: *Self

std.bit_set.Integer.setIntersection

函数

第 186 行

对两个位集执行交集,并将 结果存入第一个位集。仅当两个输入的对应位 均置位时,结果中的对应位才置位。

pub fn setIntersection(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Integer.setRangeValue

函数

第 118 行

将指定范围内所有位的值改为 给定布尔值。

pub fn setRangeValue(self: *Self, range: Range, value: bool) void

参数

self: *Self
range: Range
value: bool

std.bit_set.Integer.setUnion

函数

第 179 行

对两个位集合求并集,并将结果存储在第一个集合中。 若任一输入中的对应位已置位,则结果中的该位置位。

pub fn setUnion(self: *Self, other: Self) void

参数

self: *Self
other: Self

std.bit_set.Integer.setValue

函数

第 102 行

将位集合中指定的位 设置为与传入布尔值一致。

pub fn setValue(self: *Self, index: usize, value: bool) void

参数

self: *Self
index: usize
value: bool

std.bit_set.Integer.ShiftInt

类型

第 71 行

用于对此位集合中的掩码移位的整数类型。

std.bit_set.Integer.SingleWordIterator

类型函数

第 295 行

fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type

参数

字段

bits_remain: MaskInt

std.bit_set.Integer.SingleWordIterator.IterSelf

别名

第 297 行

别名目标 std.bit_set.Integer.SingleWordIterator

std.bit_set.Integer.SingleWordIterator.next

函数

第 303 行

按升序返回位集合中下一个尚未访问的置位索引。

pub fn next(self: *IterSelf) ?usize

参数

self: *IterSelf

std.bit_set.Integer.subsetOf

函数

第 224 行

当且仅当第一个位集合是第二个的子集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Integer.supersetOf

函数

第 230 行

当且仅当第一个位集合为第二个位集合的 超集时返回 true。

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

参数

self: Self
other: Self

std.bit_set.Integer.toggle

函数

第 150 行

翻转位集合中的指定位

pub fn toggle(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Integer.toggleAll

函数

第 162 行

翻转位集合中的每一位。

pub fn toggleAll(self: *Self) void

参数

self: *Self

std.bit_set.Integer.toggleFirstSet

函数

第 208 行

查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。

pub fn toggleFirstSet(self: *Self) ?usize

参数

self: *Self

std.bit_set.Integer.toggleSet

函数

第 157 行

翻转此位集合中所有也存在于 toggles 位集合的位。

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

参数

self: *Self
toggles: Self

std.bit_set.Integer.unionWith

函数

第 245 行

返回两个位集合的并集。 任一输入的对应位置位时, 结果的该位置位。

pub fn unionWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.Integer.unset

函数

第 142 行

从位集合中移除指定的位

pub fn unset(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.bit_set.Integer.unsetAll

函数

第 167 行

将所有位设为 0。

pub fn unsetAll(self: *Self) void

参数

self: *Self

std.bit_set.Integer.xorWith

函数

第 263 行

返回两个位集合的异或。 若两个输入的对应位不同, 结果中该位置位。

pub fn xorWith(self: Self, other: Self) Self

参数

self: Self
other: Self

std.bit_set.IntegerBitSet

别名

第 54 行

已弃用:请使用 Integer。

别名目标 std.bit_set.Integer

std.bit_set.IteratorOptions

容器

第 1284 行

配置位集合迭代器的选项。

字段

kind: Type = .set

确定应访问哪些位

direction: Direction = .forward

决定访问各位索引的顺序

std.bit_set.IteratorOptions.Direction

容器

第 1297 行

字段

forward

按升序访问索引

reverse

按降序访问索引。 注意,这可能比正向迭代的开销略高。

std.bit_set.IteratorOptions.Type

容器

第 1290 行

字段

set

访问置位位的索引

unset

遍历未设置位的索引

std.bit_set.Range

容器

第 1401 行

位集内的一段索引范围。

字段

start: usize

首个关注位的索引。

end: usize

最后一个关注位之后紧邻的索引。

std.bit_set.Static

类型函数

第 45 行

返回适合指定元素数量的最优静态位集类型: IntegerBitSet 或 ArrayBitSet, 二者实现相同接口。 返回的类型不执行任何分配, 可按值复制,且无需反初始化。

pub fn Static(comptime size: usize) type

参数

size: usize

用法示例

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

别名

第 38 行

已弃用:使用 Static。

别名目标 std.bit_set.Static

std.bit_set.std

别名

第 32 行

别名目标 std

std.bit_set.testBitSet

函数

第 1467 行

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

参数

len: usize

std.bit_set.testEql

函数

第 1412 行

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

参数

len: usize

std.bit_set.testing

别名

第 1410 行

别名目标 std.testing

std.bit_set.testPureBitSet

函数

第 1688 行

fn testPureBitSet(comptime Set: type) !void

参数

Set: type

std.bit_set.testStaticBitSet

函数

第 1741 行

fn testStaticBitSet(comptime Set: type) !void

参数

Set: type

std.bit_set.testSubsetOf

函数

第 1427 行

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

参数

len: usize

std.bit_set.testSupersetOf

函数

第 1447 行

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

参数

len: usize
源码

std/bit_set.zig

//! 此文件定义了几种位集合。位集合是对整数集合的密集存储形式,集合的最大值已知,且每个整数对应一个位。位集合的存在性检查、更新、并集和交集运算都非常快。不过,如果可能的元素数量非常大,而给定集合中的实际元素通常很少,那么它们的内存效率可能低于数组集合。
//!
//! 此处定义了五种变体:
//!
//! Integer:
//!   静态大小的位集合,由单个整数作为后备存储。
//!   适用于元素较少的集合;但集合较大时,尤其在调试模式下,可能生成效率较低的代码。
//!
//! Array:
//!   静态大小的位集合,由 usize 数组作为后备存储。
//!   适用于元素较多的集合;但集合较小时,可能占用多余字节。
//!
//! Static:
//!   根据请求的大小选择 Integer 或 Array。
//!   除字段外,这两种类型的接口完全一致。
//!
//! Dynamic:
//!   大小在运行期才确定的位集合,由已分配的 usize 切片作为后备存储。
//!
//! DynamicManaged:
//!   Dynamic 的一种变体,会存储分配器,并在需要时使用它。
//!
//!
//!
//!
//!
//!
//!
//!
//!

const std = @import("std.zig");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
const builtin = @import("builtin");

/// 已弃用:使用 `Static`。
pub const StaticBitSet = Static;

/// 返回适合指定元素数量的最优静态位集类型:
/// `IntegerBitSet` 或 `ArrayBitSet`,
/// 二者实现相同接口。
/// 返回的类型不执行任何分配,
/// 可按值复制,且无需反初始化。
pub fn Static(comptime size: usize) type {
    if (size <= @bitSizeOf(usize)) {
        return Integer(size);
    } else {
        return Array(usize, size);
    }
}

/// 已弃用:请使用 `Integer`。
pub const IntegerBitSet = Integer;

/// 以单个整数作为底层存储的固定大小位集。
/// 适合较小的集合,但对于较大的集合,
/// 可能生成低效代码,尤其在调试模式下。
pub fn Integer(comptime size: u16) type {
    return packed struct(MaskInt) {
        const Self = @This();

        // TODO: 相关问题修复后,将其改为编译期字段
        /// 此位集中的条目数量
        pub const bit_length: usize = size;

        /// 在此位集合中用于表示掩码的整数类型
        pub const MaskInt = @Int(.unsigned, size);

        /// 用于对此位集合中的掩码移位的整数类型。
        pub const ShiftInt = std.math.Log2Int(MaskInt);

        /// 将位掩码表示为单个整数
        mask: MaskInt,

        /// 不含任何元素的位集合。
        pub const empty: Self = .{ .mask = 0 };

        /// 包含所有元素的位集。
        pub const full: Self = .{ .mask = ~@as(MaskInt, 0) };

        /// 返回此位集合中的位数
        pub inline fn capacity(self: Self) usize {
            _ = self;
            return bit_length;
        }

        /// 指定索引处的位存在于集合中时返回 true,
        /// 否则返回 false。
        pub fn isSet(self: Self, index: usize) bool {
            assert(index < bit_length);
            return (self.mask & maskBit(index)) != 0;
        }

        /// 返回此位集合中已设置位的总数。
        pub fn count(self: Self) usize {
            return @popCount(self.mask);
        }

        /// 将位集合中指定的位
        /// 设置为与传入布尔值一致。
        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;
        }

        /// 向位集合添加指定位
        pub fn set(self: *Self, index: usize) void {
            assert(index < bit_length);
            self.mask |= maskBit(index);
        }

        /// 将指定范围内所有位的值改为
        /// 给定布尔值。
        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;
        }

        /// 从位集合中移除指定的位
        pub fn unset(self: *Self, index: usize) void {
            assert(index < bit_length);
            // 针对 #7953 的变通处理
            if (MaskInt == u0) return;
            self.mask &= ~maskBit(index);
        }

        /// 翻转位集合中的指定位
        pub fn toggle(self: *Self, index: usize) void {
            assert(index < bit_length);
            self.mask ^= maskBit(index);
        }

        /// 翻转此位集合中所有也存在于
        /// toggles 位集合的位。
        pub fn toggleSet(self: *Self, toggles: Self) void {
            self.mask ^= toggles.mask;
        }

        /// 翻转位集合中的每一位。
        pub fn toggleAll(self: *Self) void {
            self.mask = ~self.mask;
        }

        /// 将所有位设为 0。
        pub fn unsetAll(self: *Self) void {
            self.mask = 0;
        }

        /// 将所有位设为 1。
        pub fn setAll(self: *Self) void {
            self.mask = ~@as(MaskInt, 0);
        }

        /// 对两个位集合求并集,并将结果存储在第一个集合中。
        /// 若任一输入中的对应位已置位,则结果中的该位置位。
        ///
        pub fn setUnion(self: *Self, other: Self) void {
            self.mask |= other.mask;
        }

        /// 对两个位集执行交集,并将
        /// 结果存入第一个位集。仅当两个输入的对应位
        /// 均置位时,结果中的对应位才置位。
        pub fn setIntersection(self: *Self, other: Self) void {
            self.mask &= other.mask;
        }

        /// 查找首个置位的索引。
        /// 若没有置位,则返回 null。
        pub fn findFirstSet(self: Self) ?usize {
            const mask = self.mask;
            if (mask == 0) return null;
            return @ctz(mask);
        }

        /// 查找最后一个置位的索引。
        /// 若没有置位,则返回 null。
        pub fn findLastSet(self: Self) ?usize {
            const mask = self.mask;
            if (mask == 0) return null;
            return bit_length - @clz(mask) - 1;
        }

        /// 查找第一个已设置位的索引,并清除它。
        /// 若没有设置任何位,则返回 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;
        }

        /// 当且仅当两个位集合中的每一对
        /// 对应位都相同时,返回 true。
        pub fn eql(self: Self, other: Self) bool {
            return bit_length == 0 or self.mask == other.mask;
        }

        /// 当且仅当第一个位集合是第二个的子集时返回 true。
        ///
        pub fn subsetOf(self: Self, other: Self) bool {
            return self.intersectWith(other).eql(self);
        }

        /// 当且仅当第一个位集合为第二个位集合的
        /// 超集时返回 true。
        pub fn supersetOf(self: Self, other: Self) bool {
            return other.subsetOf(self);
        }

        /// 返回位集合的补集。若对应位原先未设置,
        /// 则结果中的该位会被设置。
        pub fn complement(self: Self) Self {
            var result = self;
            result.toggleAll();
            return result;
        }

        /// 返回两个位集合的并集。
        /// 任一输入的对应位置位时,
        /// 结果的该位置位。
        pub fn unionWith(self: Self, other: Self) Self {
            var result = self;
            result.setUnion(other);
            return result;
        }

        /// 返回两个位集合的交集。
        /// 只有两个输入中的对应位都已置位,结果中的该位才置位。
        ///
        pub fn intersectWith(self: Self, other: Self) Self {
            var result = self;
            result.setIntersection(other);
            return result;
        }

        /// 返回两个位集合的异或。
        /// 若两个输入的对应位不同,
        /// 结果中该位置位。
        pub fn xorWith(self: Self, other: Self) Self {
            var result = self;
            result.toggleSet(other);
            return result;
        }

        /// 返回两个位集合的差集。
        /// 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。
        ///
        pub fn differenceWith(self: Self, other: Self) Self {
            var result = self;
            result.setIntersection(other.complement());
            return result;
        }

        /// 根据选项遍历集合中的元素。
        /// 默认选项(.{})会按升序遍历
        /// 已置位的位索引。对底层位集合的修改
        /// 可能被迭代器观察到,也可能不会。
        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();
                // 所有尚未迭代处理的位
                bits_remain: MaskInt,

                /// 按升序返回位集合中下一个尚未访问的置位索引。
                ///
                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));
        }
    };
}

/// 已弃用:使用 `Array`。
pub const ArrayBitSet = Array;

/// 静态大小的位集合,由 usize 数组作为底层存储。
/// 适合较大的集合;但集合较小时,
/// 占用的字节数可能多于必要值。
pub fn Array(comptime MaskIntType: type, comptime size: usize) type {
    const mask_info: std.builtin.Type = @typeInfo(MaskIntType);

    // 确保掩码整数确实是整数
    if (mask_info != .int) @compileError("Array can only operate on integer masks, but was passed " ++ @typeName(MaskIntType));

    // 它还必须是无符号数。
    if (mask_info.int.signedness != .unsigned) @compileError("Array requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType));

    // 并且它不能为空。
    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;

    // 使用移位和截断,将索引分解为掩码索引和位索引。
    // 此操作要求掩码的位数恰为 2 的幂。
    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) ++ ").");
    }

    // 确保整数没有填充位。
    // 填充位在此处浪费空间,可能是用户的错误。
    // 较小的 2 的幂位宽(例如 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: 相关问题修复后,将其改为编译期字段
        /// 此位集中的条目数量
        pub const bit_length: usize = size;

        /// 在此位集合中用于表示掩码的整数类型
        pub const MaskInt = MaskIntType;

        /// 用于对此位集合中的掩码移位的整数类型。
        pub const ShiftInt = std.math.Log2Int(MaskInt);

        // 一个掩码中的位
        const mask_len = @bitSizeOf(MaskInt);
        // 掩码总数量
        const num_masks = (size + mask_len - 1) / mask_len;
        // 最后一个掩码中的填充位(可为 0)
        const last_pad_bits = mask_len * num_masks - size;
        // 最后一个掩码中的有效位掩码。
        // 所有函数都会确保最后一个掩码中的
        // 无效位为零。
        pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits;

        /// 按低索引在前的顺序排列位掩码。末尾的填充位未定义。
        ///
        masks: [num_masks]MaskInt,

        /// 不含任何元素的位集合。
        pub const empty: Self = .{ .masks = @splat(0) };

        /// 包含所有元素的位集。
        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 };
        };

        /// 返回此位集合中的位数
        pub inline fn capacity(self: Self) usize {
            _ = self;
            return bit_length;
        }

        /// 指定索引处的位存在于集合中时返回 true,
        /// 否则返回 false。
        pub fn isSet(self: Self, index: usize) bool {
            assert(index < bit_length);
            if (num_masks == 0) return false; // 这种情况下无法编译
            return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
        }

        /// 返回此位集合中已设置位的总数。
        pub fn count(self: Self) usize {
            var total: usize = 0;
            for (self.masks) |mask| {
                total += @popCount(mask);
            }
            return total;
        }

        /// 将位集合中指定的位
        /// 设置为与传入布尔值一致。
        pub fn setValue(self: *Self, index: usize, value: bool) void {
            assert(index < bit_length);
            if (num_masks == 0) return; // 这种情况下无法编译
            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;
        }

        /// 向位集合添加指定位
        pub fn set(self: *Self, index: usize) void {
            assert(index < bit_length);
            if (num_masks == 0) return; // 这种情况下无法编译
            self.masks[maskIndex(index)] |= maskBit(index);
        }

        /// 将指定范围内所有位的值改为
        /// 给定布尔值。
        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)));
                }
            }
        }

        /// 从位集合中移除指定的位
        pub fn unset(self: *Self, index: usize) void {
            assert(index < bit_length);
            if (num_masks == 0) return; // 这种情况下无法编译
            self.masks[maskIndex(index)] &= ~maskBit(index);
        }

        /// 翻转位集合中的指定位
        pub fn toggle(self: *Self, index: usize) void {
            assert(index < bit_length);
            if (num_masks == 0) return; // 这种情况下无法编译
            self.masks[maskIndex(index)] ^= maskBit(index);
        }

        /// 翻转此位集合中所有也存在于
        /// toggles 位集合的位。
        pub fn toggleSet(self: *Self, toggles: Self) void {
            for (&self.masks, 0..) |*mask, i| {
                mask.* ^= toggles.masks[i];
            }
        }

        /// 翻转位集合中的每一位。
        pub fn toggleAll(self: *Self) void {
            for (&self.masks) |*mask| {
                mask.* = ~mask.*;
            }

            // 将填充位清零
            if (num_masks > 0) {
                self.masks[num_masks - 1] &= last_item_mask;
            }
        }

        /// 将所有位设为 0。
        pub fn unsetAll(self: *Self) void {
            for (&self.masks) |*mask| {
                mask.* = 0;
            }
        }

        /// 将所有位设为 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;
            }
        }

        /// 对两个位集合求并集,并将结果存储在第一个集合中。
        /// 若任一输入中的对应位已置位,则结果中的该位置位。
        ///
        pub fn setUnion(self: *Self, other: Self) void {
            for (&self.masks, 0..) |*mask, i| {
                mask.* |= other.masks[i];
            }
        }

        /// 对两个位集执行交集,并将
        /// 结果存入第一个位集。仅当两个输入的对应位
        /// 均置位时,结果中的对应位才置位。
        pub fn setIntersection(self: *Self, other: Self) void {
            for (&self.masks, 0..) |*mask, i| {
                mask.* &= other.masks[i];
            }
        }

        /// 查找首个置位的索引。
        /// 若没有置位,则返回 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);
        }

        /// 查找最后一个置位的索引。
        /// 若没有置位,则返回 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;
        }

        /// 查找第一个已设置位的索引,并清除它。
        /// 若没有设置任何位,则返回 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;
        }

        /// 当且仅当两个位集合中的每一对
        /// 对应位都相同时,返回 true。
        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;
        }

        /// 当且仅当第一个位集合是第二个的子集时返回 true。
        ///
        pub fn subsetOf(self: Self, other: Self) bool {
            return self.intersectWith(other).eql(self);
        }

        /// 当且仅当第一个位集合为第二个位集合的
        /// 超集时返回 true。
        pub fn supersetOf(self: Self, other: Self) bool {
            return other.subsetOf(self);
        }

        /// 返回位集合的补集。若对应位原先未设置,
        /// 则结果中的该位会被设置。
        pub fn complement(self: Self) Self {
            var result = self;
            result.toggleAll();
            return result;
        }

        /// 返回两个位集合的并集。
        /// 任一输入的对应位置位时,
        /// 结果的该位置位。
        pub fn unionWith(self: Self, other: Self) Self {
            var result = self;
            result.setUnion(other);
            return result;
        }

        /// 返回两个位集合的交集。
        /// 只有两个输入中的对应位都已置位,结果中的该位才置位。
        ///
        pub fn intersectWith(self: Self, other: Self) Self {
            var result = self;
            result.setIntersection(other);
            return result;
        }

        /// 返回两个位集合的异或。
        /// 若两个输入的对应位不同,
        /// 结果中该位置位。
        pub fn xorWith(self: Self, other: Self) Self {
            var result = self;
            result.toggleSet(other);
            return result;
        }

        /// 返回两个位集合的差集。
        /// 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。
        ///
        pub fn differenceWith(self: Self, other: Self) Self {
            var result = self;
            result.setIntersection(other.complement());
            return result;
        }

        /// 根据选项遍历集合中的元素。
        /// 默认选项(.{})会按升序遍历
        /// 已置位的位索引。对底层位集合的修改
        /// 可能被迭代器观察到,也可能不会。
        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));
        }
    };
}

/// 已弃用:使用 `Dynamic`。
pub const DynamicBitSetUnmanaged = Dynamic;

/// 大小在运行期已知、由已分配 usize 切片提供存储的位集合。
/// 分配器必须由用户在外部跟踪。
pub const Dynamic = struct {
    const Self = @This();

    /// 在此位集合中用于表示掩码的整数类型
    pub const MaskInt = usize;

    /// 用于对此位集合中的掩码移位的整数类型。
    pub const ShiftInt = std.math.Log2Int(MaskInt);

    /// 此位集合中有效项的数量
    bit_length: usize = 0,

    /// 按低索引在前的顺序排列位掩码。
    /// 末尾的填充位必须清零。
    masks: [*]MaskInt = empty_masks_ptr,
    // 此指针比实际分配地址靠后一个 usize。
    // 该槽位保存真实分配大小,
    // 当缩小分配失败时,Zig 分配器接口
    // 需要使用它。
    const empty_masks_data = [_]MaskInt{ 0, undefined };
    const empty_masks_ptr = @constCast(empty_masks_data[1..2]);

    /// 创建不含任何元素的位集合。
    /// 如果 bit_length 非零,最终必须调用 deinit。
    pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
        var self = Self{};
        try self.resize(allocator, bit_length, false);
        return self;
    }

    /// 创建包含所有元素的位集合。
    /// 若 bit_length 非零,最终必须调用 deinit。
    pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
        var self = Self{};
        try self.resize(allocator, bit_length, true);
        return self;
    }

    /// 调整为新的 bit_length。若新长度大于
    /// 旧长度,则使用 `fill` 填充新增位。
    /// 若 new_len 非零,最终必须调用 deinit。
    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: {
            // realloc 失败可能表示两种情况。
            // 若正在扩容,则表示内存不足。
            // 若正在缩容,则表示分配器不希望
            // 移动该分配。这意味着必须
            // 保留所需的额外 8 字节,以便
            // 正确释放此分配。
            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 (new_len > old_len) {
            // 将原末项中的填充位设为 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;
            }

            // 填充所有新掩码
            if (new_masks > old_masks) {
                const fill_value = std.math.boolMask(MaskInt, fill);
                @memset(self.masks[old_masks..new_masks], fill_value);
            }
        }

        // 将填充位清零
        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;
        }

        // 最后保存新长度。
        self.bit_length = new_len;
    }

    /// 反初始化数组并释放其内存。
    /// 传入的分配器必须与此前用于
    /// init* 或 resize 的分配器相同。
    pub fn deinit(self: *Self, allocator: Allocator) void {
        self.resize(allocator, 0, false) catch unreachable;
    }

    /// 使用新分配器创建此位集合的副本。
    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;
    }

    /// 返回此位集合中的位数
    pub inline fn capacity(self: Self) usize {
        return self.bit_length;
    }

    /// 指定索引处的位存在于集合中时返回 true,
    /// 否则返回 false。
    pub fn isSet(self: Self, index: usize) bool {
        assert(index < self.bit_length);
        return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
    }

    /// 返回此位集合中已设置位的总数。
    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| {
            // 注意:此处依赖填充位为零
            total += @popCount(mask);
        }
        return total;
    }

    /// 将位集合中指定的位
    /// 设置为与传入布尔值一致。
    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;
    }

    /// 向位集合添加指定位
    pub fn set(self: *Self, index: usize) void {
        assert(index < self.bit_length);
        self.masks[maskIndex(index)] |= maskBit(index);
    }

    /// 将指定范围内所有位的值改为
    /// 给定布尔值。
    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)));
            }
        }
    }

    /// 从位集合中移除指定的位
    pub fn unset(self: *Self, index: usize) void {
        assert(index < self.bit_length);
        self.masks[maskIndex(index)] &= ~maskBit(index);
    }

    /// 将所有位设为 0。
    pub fn unsetAll(self: *Self) void {
        const masks_len = numMasks(self.bit_length);
        @memset(self.masks[0..masks_len], 0);
    }

    /// 将所有位设为 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;
        }
    }

    /// 翻转位集合中的指定位
    pub fn toggle(self: *Self, index: usize) void {
        assert(index < self.bit_length);
        self.masks[maskIndex(index)] ^= maskBit(index);
    }

    /// 翻转此位集合中在 toggles 位集合中出现的所有位。
    /// 两个集合必须具有相同 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];
        }
    }

    /// 翻转位集合中的每一位。
    pub fn toggleAll(self: *Self) void {
        const bit_length = self.bit_length;
        // bit_length 为零时避免下溢
        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;
    }

    /// 对两个位集执行并集,并将
    /// 结果存入第一个位集。任一输入中的对应位置位时,
    /// 结果中的对应位即置位。
    /// 两个位集必须具有相同的 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];
        }
    }

    /// 计算两个位集合的交集,并将结果
    /// 存入第一个集合。仅当两个输入中的对应位
    /// 均已置位时,结果中的该位才置位。
    /// 两个集合的 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];
        }
    }

    /// 查找首个置位的索引。
    /// 若没有置位,则返回 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]);
    }

    /// 查找最后一个置位的索引。
    /// 若没有置位,则返回 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;
    }

    /// 查找第一个已设置位的索引,并清除它。
    /// 若没有设置任何位,则返回 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;
    }

    /// 当且仅当两个位集合中的每一对
    /// 对应位都相同时,返回 true。
    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;
    }

    /// 当且仅当第一个位集合是第二个的子集时返回 true。
    ///
    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;
    }

    /// 当且仅当第一个位集合为第二个位集合的
    /// 超集时返回 true。
    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;
    }

    /// 按选项遍历集合中的元素。
    /// 默认选项 .{} 按升序遍历已设置位的索引。
    /// 迭代器可能观察到对底层位集的修改,也可能观察不到。
    /// 调整底层位集大小会使迭代器失效。
    ///
    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);
    }
};

/// 已弃用:使用 `DynamicManaged` 或 `Dynamic`(需要更新调用位置)。
pub const DynamicBitSet = DynamicManaged;

/// 大小在运行时已知的位集,以已分配的 usize
/// 切片作为底层存储。对 Dynamic 的轻量封装,
/// 用于跟踪分配器实例。
///
/// 已弃用,请改用 `Dynamic`;后者在需要时接受
/// `Allocator` 参数,而不存储它。
pub const DynamicManaged = struct {
    const Self = @This();

    /// 在此位集合中用于表示掩码的整数类型
    pub const MaskInt = usize;

    /// 用于对此位集合中的掩码移位的整数类型。
    pub const ShiftInt = std.math.Log2Int(MaskInt);

    allocator: Allocator,
    unmanaged: Dynamic = .{},

    /// 创建不含任何元素的位集。
    pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
        return Self{
            .unmanaged = try .initEmpty(allocator, bit_length),
            .allocator = allocator,
        };
    }

    /// 创建包含所有元素的位集。
    pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
        return Self{
            .unmanaged = try .initFull(allocator, bit_length),
            .allocator = allocator,
        };
    }

    /// 调整为新长度。如果新长度大于
    /// 旧长度,则用 `fill` 填充新增位。
    pub fn resize(self: *@This(), new_len: usize, fill: bool) !void {
        try self.unmanaged.resize(self.allocator, new_len, fill);
    }

    /// 反初始化数组并释放其内存。
    /// 传入的分配器必须与此前用于
    /// init* 或 resize 的分配器相同。
    pub fn deinit(self: *Self) void {
        self.unmanaged.deinit(self.allocator);
    }

    /// 使用新分配器创建此位集合的副本。
    pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
        return Self{
            .unmanaged = try self.unmanaged.clone(new_allocator),
            .allocator = new_allocator,
        };
    }

    /// 返回此位集合中的位数
    pub inline fn capacity(self: Self) usize {
        return self.unmanaged.capacity();
    }

    /// 指定索引处的位存在于集合中时返回 true,
    /// 否则返回 false。
    pub fn isSet(self: Self, index: usize) bool {
        return self.unmanaged.isSet(index);
    }

    /// 返回此位集合中已设置位的总数。
    pub fn count(self: Self) usize {
        return self.unmanaged.count();
    }

    /// 将位集合中指定的位
    /// 设置为与传入布尔值一致。
    pub fn setValue(self: *Self, index: usize, value: bool) void {
        self.unmanaged.setValue(index, value);
    }

    /// 向位集合添加指定位
    pub fn set(self: *Self, index: usize) void {
        self.unmanaged.set(index);
    }

    /// 将指定范围内所有位的值改为
    /// 给定布尔值。
    pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
        self.unmanaged.setRangeValue(range, value);
    }

    /// 从位集合中移除指定的位
    pub fn unset(self: *Self, index: usize) void {
        self.unmanaged.unset(index);
    }

    /// 翻转位集合中的指定位
    pub fn toggle(self: *Self, index: usize) void {
        self.unmanaged.toggle(index);
    }

    /// 翻转此位集合中在 toggles 位集合中出现的所有位。
    /// 两个集合必须具有相同 bit_length。
    ///
    pub fn toggleSet(self: *Self, toggles: Self) void {
        self.unmanaged.toggleSet(toggles.unmanaged);
    }

    /// 翻转位集合中的每一位。
    pub fn toggleAll(self: *Self) void {
        self.unmanaged.toggleAll();
    }

    /// 对两个位集执行并集,并将
    /// 结果存入第一个位集。任一输入中的对应位置位时,
    /// 结果中的对应位即置位。
    /// 两个位集必须具有相同的 bit_length。
    pub fn setUnion(self: *Self, other: Self) void {
        self.unmanaged.setUnion(other.unmanaged);
    }

    /// 计算两个位集合的交集,并将结果
    /// 存入第一个集合。仅当两个输入中的对应位
    /// 均已置位时,结果中的该位才置位。
    /// 两个集合的 bit_length 必须相同。
    pub fn setIntersection(self: *Self, other: Self) void {
        self.unmanaged.setIntersection(other.unmanaged);
    }

    /// 将所有位设为 0。
    pub fn unsetAll(self: *Self) void {
        self.unmanaged.unsetAll();
    }

    /// 将所有位设为 1。
    pub fn setAll(self: *Self) void {
        self.unmanaged.setAll();
    }

    /// 查找首个置位的索引。
    /// 若没有置位,则返回 null。
    pub fn findFirstSet(self: Self) ?usize {
        return self.unmanaged.findFirstSet();
    }

    /// 查找最后一个置位的索引。
    /// 若没有置位,则返回 null。
    pub fn findLastSet(self: Self) ?usize {
        return self.unmanaged.findLastSet();
    }

    /// 查找第一个已设置位的索引,并清除它。
    /// 若没有设置任何位,则返回 null。
    pub fn toggleFirstSet(self: *Self) ?usize {
        return self.unmanaged.toggleFirstSet();
    }

    /// 当且仅当两个位集合中的每一对
    /// 对应位都相同时,返回 true。
    pub fn eql(self: Self, other: Self) bool {
        return self.unmanaged.eql(other.unmanaged);
    }

    /// 按选项遍历集合中的元素。
    /// 默认选项 .{} 按升序遍历已设置位的索引。
    /// 迭代器可能观察到对底层位集的修改,也可能观察不到。
    /// 调整底层位集大小会使迭代器失效。
    ///
    pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
        return self.unmanaged.iterator(options);
    }

    pub const Iterator = Dynamic.Iterator;
};

/// 配置位集合迭代器的选项。
pub const IteratorOptions = struct {
    /// 确定应访问哪些位
    kind: Type = .set,
    /// 决定访问各位索引的顺序
    direction: Direction = .forward,

    pub const Type = enum {
        /// 访问置位位的索引
        set,
        /// 遍历未设置位的索引
        unset,
    };

    pub const Direction = enum {
        /// 按升序访问索引
        forward,
        /// 按降序访问索引。
        /// 注意,这可能比正向迭代的开销略高。
        reverse,
    };
};

// 此迭代器可在多种位集合类型之间复用
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();

        // 所有尚未迭代处理的位
        bits_remain: MaskInt,
        // 所有尚未迭代的字
        words_remain: []const MaskInt,
        // 当前字的偏移量
        bit_offset: usize,
        // 最后一个字的掩码
        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;
            }
        }

        /// 按升序返回位集合中下一个尚未访问的置位索引。
        ///
        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;
                },
            }
        }

        // 加载下一个字。不存在下一个字时不得调用。若下一个字是最后一个字,则屏蔽填充位,以免访问它们。
        //
        //
        //
        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;
        }
    };
}

/// 位集内的一段索引范围。
pub const Range = struct {
    /// 首个关注位的索引。
    start: usize,
    /// 最后一个关注位之后紧邻的索引。
    end: usize,
};

// ---------------- 测试 -----------------

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); // 将 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); // 将 a 清零
        tmp.toggleSet(tmp); // 将 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));
}