此文件定义了几种位集合。位集合是对整数集合的密集存储形式,集合的最大值已知,且每个整数对应一个位。位集合的存在性检查、更新、并集和交集运算都非常快。不过,如果可能的元素数量非常大,而给定集合中的实际元素通常很少,那么它们的内存效率可能低于数组集合。
此处定义了五种变体:
Integer: 静态大小的位集合,由单个整数作为后备存储。 适用于元素较少的集合;但集合较大时,尤其在调试模式下,可能生成效率较低的代码。
Array: 静态大小的位集合,由 usize 数组作为后备存储。 适用于元素较多的集合;但集合较小时,可能占用多余字节。
Static: 根据请求的大小选择 Integer 或 Array。 除字段外,这两种类型的接口完全一致。
Dynamic: 大小在运行期才确定的位集合,由已分配的 usize 切片作为后备存储。
DynamicManaged: Dynamic 的一种变体,会存储分配器,并在需要时使用它。
std.bit_set.Allocator
别名
别名目标 std.mem.Allocator
std.bit_set.Array
类型函数
静态大小的位集合,由 usize 数组作为底层存储。 适合较大的集合;但集合较小时, 占用的字节数可能多于必要值。
pub fn Array(comptime MaskIntType: type, comptime size: usize) type
参数
MaskIntType: type
size: usize
字段
Selfbit_lengthMaskIntShiftIntmask_lennum_maskslast_pad_bitslast_item_maskemptyfullcapacityisSetcountsetValuesetsetRangeValueunsettoggletoggleSettoggleAllunsetAllsetAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfcomplementunionWithintersectWithxorWithdifferenceWithiteratorIteratormaskBitmaskIndexboolMaskBit
用法示例
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
常量
此位集中的条目数量
usize
std.bit_set.Array.boolMaskBit
函数
fn boolMaskBit(index: usize, value: bool) MaskInt
参数
index: usize
value: bool
std.bit_set.Array.capacity
函数
返回此位集合中的位数
pub inline fn capacity(self: Self) usize
参数
self: Self
std.bit_set.Array.complement
函数
返回位集合的补集。若对应位原先未设置, 则结果中的该位会被设置。
pub fn complement(self: Self) Self
参数
self: Self
std.bit_set.Array.count
函数
返回此位集合中已设置位的总数。
pub fn count(self: Self) usize
参数
self: Self
std.bit_set.Array.differenceWith
函数
返回两个位集合的差集。 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。
pub fn differenceWith(self: Self, other: Self) Self
参数
std.bit_set.Array.empty
常量
不含任何元素的位集合。
Self
std.bit_set.Array.eql
函数
当且仅当两个位集合中的每一对 对应位都相同时,返回 true。
pub fn eql(self: Self, other: Self) bool
参数
std.bit_set.Array.findFirstSet
函数
查找首个置位的索引。 若没有置位,则返回 null。
pub fn findFirstSet(self: Self) ?usize
参数
self: Self
std.bit_set.Array.findLastSet
函数
查找最后一个置位的索引。 若没有置位,则返回 null。
pub fn findLastSet(self: Self) ?usize
参数
self: Self
std.bit_set.Array.full
常量
包含所有元素的位集。
Self
std.bit_set.Array.intersectWith
函数
返回两个位集合的交集。 只有两个输入中的对应位都已置位,结果中的该位才置位。
pub fn intersectWith(self: Self, other: Self) Self
参数
std.bit_set.Array.isSet
函数
指定索引处的位存在于集合中时返回 true, 否则返回 false。
pub fn isSet(self: Self, index: usize) bool
参数
self: Self
index: usize
std.bit_set.Array.iterator
函数
根据选项遍历集合中的元素。 默认选项(.{})会按升序遍历 已置位的位索引。对底层位集合的修改 可能被迭代器观察到,也可能不会。
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
参数
self: *const Self
options: IteratorOptions
std.bit_set.Array.Iterator
类型函数
pub fn Iterator(comptime options: IteratorOptions) type
参数
options: IteratorOptions
std.bit_set.Array.last_item_mask
常量
std.bit_set.Array.last_pad_bits
常量
std.bit_set.Array.mask_len
常量
std.bit_set.Array.maskBit
函数
fn maskBit(index: usize) MaskInt
参数
index: usize
std.bit_set.Array.maskIndex
函数
fn maskIndex(index: usize) usize
参数
index: usize
std.bit_set.Array.MaskInt
常量
在此位集合中用于表示掩码的整数类型
std.bit_set.Array.num_masks
常量
std.bit_set.Array.Self
别名
别名目标 std.bit_set.Array
std.bit_set.Array.set
函数
向位集合添加指定位
pub fn set(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Array.setAll
函数
将所有位设为 1。
pub fn setAll(self: *Self) void
参数
self: *Self
std.bit_set.Array.setIntersection
函数
对两个位集执行交集,并将 结果存入第一个位集。仅当两个输入的对应位 均置位时,结果中的对应位才置位。
pub fn setIntersection(self: *Self, other: Self) void
参数
std.bit_set.Array.setRangeValue
函数
将指定范围内所有位的值改为 给定布尔值。
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
参数
std.bit_set.Array.setUnion
函数
对两个位集合求并集,并将结果存储在第一个集合中。 若任一输入中的对应位已置位,则结果中的该位置位。
pub fn setUnion(self: *Self, other: Self) void
参数
std.bit_set.Array.setValue
函数
将位集合中指定的位 设置为与传入布尔值一致。
pub fn setValue(self: *Self, index: usize, value: bool) void
参数
std.bit_set.Array.ShiftInt
类型
用于对此位集合中的掩码移位的整数类型。
std.bit_set.Array.subsetOf
函数
当且仅当第一个位集合是第二个的子集时返回 true。
pub fn subsetOf(self: Self, other: Self) bool
参数
std.bit_set.Array.supersetOf
函数
当且仅当第一个位集合为第二个位集合的 超集时返回 true。
pub fn supersetOf(self: Self, other: Self) bool
参数
std.bit_set.Array.toggle
函数
翻转位集合中的指定位
pub fn toggle(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Array.toggleAll
函数
翻转位集合中的每一位。
pub fn toggleAll(self: *Self) void
参数
self: *Self
std.bit_set.Array.toggleFirstSet
函数
查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。
pub fn toggleFirstSet(self: *Self) ?usize
参数
self: *Self
std.bit_set.Array.toggleSet
函数
翻转此位集合中所有也存在于 toggles 位集合的位。
pub fn toggleSet(self: *Self, toggles: Self) void
参数
std.bit_set.Array.unionWith
函数
返回两个位集合的并集。 任一输入的对应位置位时, 结果的该位置位。
pub fn unionWith(self: Self, other: Self) Self
参数
std.bit_set.Array.unset
函数
从位集合中移除指定的位
pub fn unset(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Array.unsetAll
函数
将所有位设为 0。
pub fn unsetAll(self: *Self) void
参数
self: *Self
std.bit_set.Array.xorWith
函数
返回两个位集合的异或。 若两个输入的对应位不同, 结果中该位置位。
pub fn xorWith(self: Self, other: Self) Self
参数
std.bit_set.ArrayBitSet
别名
已弃用:使用 Array。
别名目标 std.bit_set.Array
std.bit_set.assert
别名
别名目标 std.debug.assert
std.bit_set.builtin
常量
std.bit_set.Dynamic
容器
大小在运行期已知、由已分配 usize 切片提供存储的位集合。 分配器必须由用户在外部跟踪。
字段
SelfMaskIntShiftIntempty_masks_dataempty_masks_ptrinitEmptyinitFullresizedeinitclonecapacityisSetcountsetValuesetsetRangeValueunsetunsetAllsetAlltoggletoggleSettoggleAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfiteratorIteratormaskBitmaskIndexboolMaskBitnumMasks
std.bit_set.Dynamic.boolMaskBit
函数
fn boolMaskBit(index: usize, value: bool) MaskInt
参数
index: usize
value: bool
std.bit_set.Dynamic.capacity
函数
返回此位集合中的位数
pub inline fn capacity(self: Self) usize
参数
self: Self
std.bit_set.Dynamic.clone
函数
使用新分配器创建此位集合的副本。
pub fn clone(self: *const Self, new_allocator: Allocator) !Self
参数
std.bit_set.Dynamic.count
函数
返回此位集合中已设置位的总数。
pub fn count(self: Self) usize
参数
self: Self
std.bit_set.Dynamic.deinit
函数
反初始化数组并释放其内存。 传入的分配器必须与此前用于 init* 或 resize 的分配器相同。
pub fn deinit(self: *Self, allocator: Allocator) void
参数
std.bit_set.Dynamic.empty_masks_data
常量
std.bit_set.Dynamic.empty_masks_ptr
常量
std.bit_set.Dynamic.eql
函数
当且仅当两个位集合中的每一对 对应位都相同时,返回 true。
pub fn eql(self: Self, other: Self) bool
参数
std.bit_set.Dynamic.findFirstSet
函数
查找首个置位的索引。 若没有置位,则返回 null。
pub fn findFirstSet(self: Self) ?usize
参数
self: Self
std.bit_set.Dynamic.findLastSet
函数
查找最后一个置位的索引。 若没有置位,则返回 null。
pub fn findLastSet(self: Self) ?usize
参数
self: Self
std.bit_set.Dynamic.initEmpty
函数
创建不含任何元素的位集合。 如果 bit_length 非零,最终必须调用 deinit。
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self
参数
allocator: Allocator
bit_length: usize
std.bit_set.Dynamic.initFull
函数
创建包含所有元素的位集合。 若 bit_length 非零,最终必须调用 deinit。
pub fn initFull(allocator: Allocator, bit_length: usize) !Self
参数
allocator: Allocator
bit_length: usize
std.bit_set.Dynamic.isSet
函数
指定索引处的位存在于集合中时返回 true, 否则返回 false。
pub fn isSet(self: Self, index: usize) bool
参数
self: Self
index: usize
std.bit_set.Dynamic.iterator
函数
按选项遍历集合中的元素。 默认选项 .{} 按升序遍历已设置位的索引。 迭代器可能观察到对底层位集的修改,也可能观察不到。 调整底层位集大小会使迭代器失效。
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
参数
self: *const Self
options: IteratorOptions
std.bit_set.Dynamic.Iterator
类型函数
pub fn Iterator(comptime options: IteratorOptions) type
参数
options: IteratorOptions
std.bit_set.Dynamic.maskBit
函数
fn maskBit(index: usize) MaskInt
参数
index: usize
std.bit_set.Dynamic.maskIndex
函数
fn maskIndex(index: usize) usize
参数
index: usize
std.bit_set.Dynamic.MaskInt
类型
在此位集合中用于表示掩码的整数类型
std.bit_set.Dynamic.numMasks
函数
fn numMasks(bit_length: usize) usize
参数
bit_length: usize
std.bit_set.Dynamic.resize
函数
调整为新的 bit_length。若新长度大于
旧长度,则使用 fill 填充新增位。
若 new_len 非零,最终必须调用 deinit。
pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void
参数
std.bit_set.Dynamic.Self
别名
别名目标 std.bit_set.Dynamic
std.bit_set.Dynamic.set
函数
向位集合添加指定位
pub fn set(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Dynamic.setAll
函数
将所有位设为 1。
pub fn setAll(self: *Self) void
参数
self: *Self
std.bit_set.Dynamic.setIntersection
函数
计算两个位集合的交集,并将结果 存入第一个集合。仅当两个输入中的对应位 均已置位时,结果中的该位才置位。 两个集合的 bit_length 必须相同。
pub fn setIntersection(self: *Self, other: Self) void
参数
std.bit_set.Dynamic.setRangeValue
函数
将指定范围内所有位的值改为 给定布尔值。
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
参数
std.bit_set.Dynamic.setUnion
函数
对两个位集执行并集,并将 结果存入第一个位集。任一输入中的对应位置位时, 结果中的对应位即置位。 两个位集必须具有相同的 bit_length。
pub fn setUnion(self: *Self, other: Self) void
参数
std.bit_set.Dynamic.setValue
函数
将位集合中指定的位 设置为与传入布尔值一致。
pub fn setValue(self: *Self, index: usize, value: bool) void
参数
std.bit_set.Dynamic.ShiftInt
类型
用于对此位集合中的掩码移位的整数类型。
std.bit_set.Dynamic.subsetOf
函数
当且仅当第一个位集合是第二个的子集时返回 true。
pub fn subsetOf(self: Self, other: Self) bool
参数
std.bit_set.Dynamic.supersetOf
函数
当且仅当第一个位集合为第二个位集合的 超集时返回 true。
pub fn supersetOf(self: Self, other: Self) bool
参数
std.bit_set.Dynamic.toggle
函数
翻转位集合中的指定位
pub fn toggle(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Dynamic.toggleAll
函数
翻转位集合中的每一位。
pub fn toggleAll(self: *Self) void
参数
self: *Self
std.bit_set.Dynamic.toggleFirstSet
函数
查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。
pub fn toggleFirstSet(self: *Self) ?usize
参数
self: *Self
std.bit_set.Dynamic.toggleSet
函数
翻转此位集合中在 toggles 位集合中出现的所有位。 两个集合必须具有相同 bit_length。
pub fn toggleSet(self: *Self, toggles: Self) void
参数
std.bit_set.Dynamic.unset
函数
从位集合中移除指定的位
pub fn unset(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Dynamic.unsetAll
函数
将所有位设为 0。
pub fn unsetAll(self: *Self) void
参数
self: *Self
std.bit_set.DynamicBitSet
别名
已弃用:使用 DynamicManaged 或 Dynamic(需要更新调用位置)。
std.bit_set.DynamicBitSetUnmanaged
别名
已弃用:使用 Dynamic。
别名目标 std.bit_set.Dynamic
std.bit_set.DynamicManaged
容器
大小在运行时已知的位集,以已分配的 usize 切片作为底层存储。对 Dynamic 的轻量封装, 用于跟踪分配器实例。
字段
std.bit_set.DynamicManaged.capacity
函数
返回此位集合中的位数
pub inline fn capacity(self: Self) usize
参数
self: Self
std.bit_set.DynamicManaged.clone
函数
使用新分配器创建此位集合的副本。
pub fn clone(self: *const Self, new_allocator: Allocator) !Self
参数
std.bit_set.DynamicManaged.count
函数
返回此位集合中已设置位的总数。
pub fn count(self: Self) usize
参数
self: Self
std.bit_set.DynamicManaged.deinit
函数
反初始化数组并释放其内存。 传入的分配器必须与此前用于 init* 或 resize 的分配器相同。
pub fn deinit(self: *Self) void
参数
self: *Self
std.bit_set.DynamicManaged.eql
函数
当且仅当两个位集合中的每一对 对应位都相同时,返回 true。
pub fn eql(self: Self, other: Self) bool
参数
std.bit_set.DynamicManaged.findFirstSet
函数
查找首个置位的索引。 若没有置位,则返回 null。
pub fn findFirstSet(self: Self) ?usize
参数
self: Self
std.bit_set.DynamicManaged.findLastSet
函数
查找最后一个置位的索引。 若没有置位,则返回 null。
pub fn findLastSet(self: Self) ?usize
参数
self: Self
std.bit_set.DynamicManaged.initEmpty
函数
创建不含任何元素的位集。
pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self
参数
allocator: Allocator
bit_length: usize
std.bit_set.DynamicManaged.initFull
函数
创建包含所有元素的位集。
pub fn initFull(allocator: Allocator, bit_length: usize) !Self
参数
allocator: Allocator
bit_length: usize
std.bit_set.DynamicManaged.isSet
函数
指定索引处的位存在于集合中时返回 true, 否则返回 false。
pub fn isSet(self: Self, index: usize) bool
参数
self: Self
index: usize
std.bit_set.DynamicManaged.iterator
函数
按选项遍历集合中的元素。 默认选项 .{} 按升序遍历已设置位的索引。 迭代器可能观察到对底层位集的修改,也可能观察不到。 调整底层位集大小会使迭代器失效。
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
参数
self: *const Self
options: IteratorOptions
std.bit_set.DynamicManaged.Iterator
别名
std.bit_set.DynamicManaged.MaskInt
类型
在此位集合中用于表示掩码的整数类型
std.bit_set.DynamicManaged.resize
函数
调整为新长度。如果新长度大于
旧长度,则用 fill 填充新增位。
pub fn resize(self: *@This(), new_len: usize, fill: bool) !void
参数
self: *@This()
new_len: usize
fill: bool
std.bit_set.DynamicManaged.Self
别名
std.bit_set.DynamicManaged.set
函数
向位集合添加指定位
pub fn set(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.DynamicManaged.setAll
函数
将所有位设为 1。
pub fn setAll(self: *Self) void
参数
self: *Self
std.bit_set.DynamicManaged.setIntersection
函数
计算两个位集合的交集,并将结果 存入第一个集合。仅当两个输入中的对应位 均已置位时,结果中的该位才置位。 两个集合的 bit_length 必须相同。
pub fn setIntersection(self: *Self, other: Self) void
参数
std.bit_set.DynamicManaged.setRangeValue
函数
将指定范围内所有位的值改为 给定布尔值。
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
参数
std.bit_set.DynamicManaged.setUnion
函数
对两个位集执行并集,并将 结果存入第一个位集。任一输入中的对应位置位时, 结果中的对应位即置位。 两个位集必须具有相同的 bit_length。
pub fn setUnion(self: *Self, other: Self) void
参数
std.bit_set.DynamicManaged.setValue
函数
将位集合中指定的位 设置为与传入布尔值一致。
pub fn setValue(self: *Self, index: usize, value: bool) void
参数
std.bit_set.DynamicManaged.ShiftInt
类型
用于对此位集合中的掩码移位的整数类型。
std.bit_set.DynamicManaged.toggle
函数
翻转位集合中的指定位
pub fn toggle(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.DynamicManaged.toggleAll
函数
翻转位集合中的每一位。
pub fn toggleAll(self: *Self) void
参数
self: *Self
std.bit_set.DynamicManaged.toggleFirstSet
函数
查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。
pub fn toggleFirstSet(self: *Self) ?usize
参数
self: *Self
std.bit_set.DynamicManaged.toggleSet
函数
翻转此位集合中在 toggles 位集合中出现的所有位。 两个集合必须具有相同 bit_length。
pub fn toggleSet(self: *Self, toggles: Self) void
参数
std.bit_set.DynamicManaged.unset
函数
从位集合中移除指定的位
pub fn unset(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.DynamicManaged.unsetAll
函数
将所有位设为 0。
pub fn unsetAll(self: *Self) void
参数
self: *Self
std.bit_set.fillEven
函数
fn fillEven(set: anytype, len: usize) void
参数
len: usize
std.bit_set.fillOdd
函数
fn fillOdd(set: anytype, len: usize) void
参数
len: usize
std.bit_set.GenericIterator
类型函数
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
函数
fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self
参数
masks: []const MaskInt
last_word_mask: MaskInt
std.bit_set.GenericIterator.next
函数
按升序返回位集合中下一个尚未访问的置位索引。
pub fn next(self: *Self) ?usize
参数
self: *Self
std.bit_set.GenericIterator.nextWord
函数
inline fn nextWord(self: *Self, comptime is_first_word: bool) void
参数
self: *Self
is_first_word: bool
std.bit_set.GenericIterator.Self
别名
std.bit_set.Integer
类型函数
以单个整数作为底层存储的固定大小位集。 适合较小的集合,但对于较大的集合, 可能生成低效代码,尤其在调试模式下。
pub fn Integer(comptime size: u16) type
参数
size: u16
字段
mask: MaskInt将位掩码表示为单个整数
Selfbit_lengthMaskIntShiftIntemptyfullcapacityisSetcountsetValuesetsetRangeValueunsettoggletoggleSettoggleAllunsetAllsetAllsetUnionsetIntersectionfindFirstSetfindLastSettoggleFirstSeteqlsubsetOfsupersetOfcomplementunionWithintersectWithxorWithdifferenceWithiteratorIteratorSingleWordIteratormaskBitboolMaskBit
用法示例
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
常量
此位集中的条目数量
usize
std.bit_set.Integer.boolMaskBit
函数
fn boolMaskBit(index: usize, value: bool) MaskInt
参数
index: usize
value: bool
std.bit_set.Integer.capacity
函数
返回此位集合中的位数
pub inline fn capacity(self: Self) usize
参数
self: Self
std.bit_set.Integer.complement
函数
返回位集合的补集。若对应位原先未设置, 则结果中的该位会被设置。
pub fn complement(self: Self) Self
参数
self: Self
std.bit_set.Integer.count
函数
返回此位集合中已设置位的总数。
pub fn count(self: Self) usize
参数
self: Self
std.bit_set.Integer.differenceWith
函数
返回两个位集合的差集。 若某位在第一个集合中置位、但在第二个集合中未置位,则结果中该位置位。
pub fn differenceWith(self: Self, other: Self) Self
参数
std.bit_set.Integer.empty
常量
不含任何元素的位集合。
Self
std.bit_set.Integer.eql
函数
当且仅当两个位集合中的每一对 对应位都相同时,返回 true。
pub fn eql(self: Self, other: Self) bool
参数
std.bit_set.Integer.findFirstSet
函数
查找首个置位的索引。 若没有置位,则返回 null。
pub fn findFirstSet(self: Self) ?usize
参数
self: Self
std.bit_set.Integer.findLastSet
函数
查找最后一个置位的索引。 若没有置位,则返回 null。
pub fn findLastSet(self: Self) ?usize
参数
self: Self
std.bit_set.Integer.full
常量
包含所有元素的位集。
Self
std.bit_set.Integer.intersectWith
函数
返回两个位集合的交集。 只有两个输入中的对应位都已置位,结果中的该位才置位。
pub fn intersectWith(self: Self, other: Self) Self
参数
std.bit_set.Integer.isSet
函数
指定索引处的位存在于集合中时返回 true, 否则返回 false。
pub fn isSet(self: Self, index: usize) bool
参数
self: Self
index: usize
std.bit_set.Integer.iterator
函数
根据选项遍历集合中的元素。 默认选项(.{})会按升序遍历 已置位的位索引。对底层位集合的修改 可能被迭代器观察到,也可能不会。
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options)
参数
self: *const Self
options: IteratorOptions
std.bit_set.Integer.Iterator
类型函数
pub fn Iterator(comptime options: IteratorOptions) type
参数
options: IteratorOptions
std.bit_set.Integer.maskBit
函数
fn maskBit(index: usize) MaskInt
参数
index: usize
std.bit_set.Integer.MaskInt
常量
在此位集合中用于表示掩码的整数类型
std.bit_set.Integer.Self
别名
别名目标 std.bit_set.Integer
std.bit_set.Integer.set
函数
向位集合添加指定位
pub fn set(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Integer.setAll
函数
将所有位设为 1。
pub fn setAll(self: *Self) void
参数
self: *Self
std.bit_set.Integer.setIntersection
函数
对两个位集执行交集,并将 结果存入第一个位集。仅当两个输入的对应位 均置位时,结果中的对应位才置位。
pub fn setIntersection(self: *Self, other: Self) void
参数
std.bit_set.Integer.setRangeValue
函数
将指定范围内所有位的值改为 给定布尔值。
pub fn setRangeValue(self: *Self, range: Range, value: bool) void
参数
std.bit_set.Integer.setUnion
函数
对两个位集合求并集,并将结果存储在第一个集合中。 若任一输入中的对应位已置位,则结果中的该位置位。
pub fn setUnion(self: *Self, other: Self) void
参数
std.bit_set.Integer.setValue
函数
将位集合中指定的位 设置为与传入布尔值一致。
pub fn setValue(self: *Self, index: usize, value: bool) void
参数
std.bit_set.Integer.ShiftInt
类型
用于对此位集合中的掩码移位的整数类型。
std.bit_set.Integer.SingleWordIterator
类型函数
fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type
参数
direction: IteratorOptions.Direction
字段
bits_remain: MaskInt
std.bit_set.Integer.SingleWordIterator.IterSelf
别名
std.bit_set.Integer.SingleWordIterator.next
函数
按升序返回位集合中下一个尚未访问的置位索引。
pub fn next(self: *IterSelf) ?usize
参数
self: *IterSelf
std.bit_set.Integer.subsetOf
函数
当且仅当第一个位集合是第二个的子集时返回 true。
pub fn subsetOf(self: Self, other: Self) bool
参数
std.bit_set.Integer.supersetOf
函数
当且仅当第一个位集合为第二个位集合的 超集时返回 true。
pub fn supersetOf(self: Self, other: Self) bool
参数
std.bit_set.Integer.toggle
函数
翻转位集合中的指定位
pub fn toggle(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Integer.toggleAll
函数
翻转位集合中的每一位。
pub fn toggleAll(self: *Self) void
参数
self: *Self
std.bit_set.Integer.toggleFirstSet
函数
查找第一个已设置位的索引,并清除它。 若没有设置任何位,则返回 null。
pub fn toggleFirstSet(self: *Self) ?usize
参数
self: *Self
std.bit_set.Integer.toggleSet
函数
翻转此位集合中所有也存在于 toggles 位集合的位。
pub fn toggleSet(self: *Self, toggles: Self) void
参数
std.bit_set.Integer.unionWith
函数
返回两个位集合的并集。 任一输入的对应位置位时, 结果的该位置位。
pub fn unionWith(self: Self, other: Self) Self
参数
std.bit_set.Integer.unset
函数
从位集合中移除指定的位
pub fn unset(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.bit_set.Integer.unsetAll
函数
将所有位设为 0。
pub fn unsetAll(self: *Self) void
参数
self: *Self
std.bit_set.Integer.xorWith
函数
返回两个位集合的异或。 若两个输入的对应位不同, 结果中该位置位。
pub fn xorWith(self: Self, other: Self) Self
参数
std.bit_set.IntegerBitSet
别名
已弃用:请使用 Integer。
别名目标 std.bit_set.Integer
std.bit_set.IteratorOptions
容器
配置位集合迭代器的选项。
字段
std.bit_set.IteratorOptions.Direction
容器
字段
forward按升序访问索引
reverse按降序访问索引。 注意,这可能比正向迭代的开销略高。
std.bit_set.IteratorOptions.Type
容器
字段
set访问置位位的索引
unset遍历未设置位的索引
std.bit_set.Range
容器
位集内的一段索引范围。
字段
start: usize首个关注位的索引。
end: usize最后一个关注位之后紧邻的索引。
std.bit_set.Static
类型函数
返回适合指定元素数量的最优静态位集类型:
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
别名
已弃用:使用 Static。
别名目标 std.bit_set.Static
std.bit_set.std
别名
别名目标 std
std.bit_set.testBitSet
函数
fn testBitSet(a: anytype, b: anytype, len: usize) !void
参数
len: usize
std.bit_set.testEql
函数
fn testEql(empty: anytype, full: anytype, len: usize) !void
参数
len: usize
std.bit_set.testing
别名
别名目标 std.testing
std.bit_set.testPureBitSet
函数
fn testPureBitSet(comptime Set: type) !void
参数
Set: type
std.bit_set.testStaticBitSet
函数
fn testStaticBitSet(comptime Set: type) !void
参数
Set: type
std.bit_set.testSubsetOf
函数
fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void
参数
len: usize
std.bit_set.testSupersetOf
函数
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));
}