A bit set with static size, which is backed by an array of usize. This set is good for sets with a larger size, but may use more bytes than necessary if your set is small.
pub fn Array(comptime MaskIntType: type, comptime size: usize) typepub fn Array(comptime MaskIntType: type, comptime size: usize) type {
const mask_info: std.builtin.Type = @typeInfo(MaskIntType);
// Make sure the mask int is indeed an int
if (mask_info != .int) @compileError("Array can only operate on integer masks, but was passed " ++ @typeName(MaskIntType));
// It must also be unsigned.
if (mask_info.int.signedness != .unsigned) @compileError("Array requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType));
// And it must not be empty.
if (MaskIntType == u0)
@compileError("Array requires a sized integer for its mask int. u0 does not work.");
const byte_size = std.mem.byte_size_in_bits;
// We use shift and truncate to decompose indices into mask indices and bit indices.
// This operation requires that the mask has an exact power of two number of bits.
if (!std.math.isPowerOfTwo(@bitSizeOf(MaskIntType))) {
var desired_bits = std.math.ceilPowerOfTwoAssert(usize, @bitSizeOf(MaskIntType));
if (desired_bits < byte_size) desired_bits = byte_size;
const FixedMaskType = @Int(.unsigned, desired_bits);
@compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++
", which is not a power of two. Please round this up to a power of two integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
}
// Make sure the integer has no padding bits.
// Those would be wasteful here and are probably a mistake by the user.
// This case may be hit with small powers of two, like u4.
if (@bitSizeOf(MaskIntType) != @sizeOf(MaskIntType) * byte_size) {
var desired_bits = @sizeOf(MaskIntType) * byte_size;
desired_bits = std.math.ceilPowerOfTwoAssert(usize, desired_bits);
const FixedMaskType = @Int(.unsigned, desired_bits);
@compileError("Array was passed integer type " ++ @typeName(MaskIntType) ++
", which contains padding bits. Please round this up to an unpadded integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
}
return extern struct {
const Self = @This();
// TODO: Make this a comptime field once those are fixed
/// The number of items in this bit set
pub const bit_length: usize = size;
/// The integer type used to represent a mask in this bit set
pub const MaskInt = MaskIntType;
/// The integer type used to shift a mask in this bit set
pub const ShiftInt = std.math.Log2Int(MaskInt);
// bits in one mask
const mask_len = @bitSizeOf(MaskInt);
// total number of masks
const num_masks = (size + mask_len - 1) / mask_len;
// padding bits in the last mask (may be 0)
const last_pad_bits = mask_len * num_masks - size;
// Mask of valid bits in the last mask.
// All functions will ensure that the invalid
// bits in the last mask are zero.
pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits;
/// The bit masks, ordered with lower indices first.
/// Padding bits at the end are undefined.
masks: [num_masks]MaskInt,
/// A bit set with no elements present.
pub const empty: Self = .{ .masks = @splat(0) };
/// A bit set with all elements present.
pub const full: Self = full: {
var masks: [num_masks]MaskInt = @splat(~@as(MaskInt, 0));
if (num_masks > 0) masks[num_masks - 1] = last_item_mask;
break :full .{ .masks = masks };
};
/// Returns the number of bits in this bit set
pub inline fn capacity(self: Self) usize {
_ = self;
return bit_length;
}
/// Returns true if the bit at the specified index
/// is present in the set, false otherwise.
pub fn isSet(self: Self, index: usize) bool {
assert(index < bit_length);
if (num_masks == 0) return false; // doesn't compile in this case
return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
}
/// Returns the total number of set bits in this bit set.
pub fn count(self: Self) usize {
var total: usize = 0;
for (self.masks) |mask| {
total += @popCount(mask);
}
return total;
}
/// Changes the value of the specified bit of the bit
/// set to match the passed boolean.
pub fn setValue(self: *Self, index: usize, value: bool) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
const bit = maskBit(index);
const mask_index = maskIndex(index);
const new_bit = bit & std.math.boolMask(MaskInt, value);
self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
}
/// Adds a specific bit to the bit set
pub fn set(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] |= maskBit(index);
}
/// Changes the value of all bits in the specified range to
/// match the passed boolean.
pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
assert(range.end <= bit_length);
assert(range.start <= range.end);
if (range.start == range.end) return;
if (num_masks == 0) return;
const start_mask_index = maskIndex(range.start);
const start_bit = @as(ShiftInt, @truncate(range.start));
const end_mask_index = maskIndex(range.end);
const end_bit = @as(ShiftInt, @truncate(range.end));
if (start_mask_index == end_mask_index) {
var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
var mask2 = std.math.boolMask(MaskInt, true) >> (mask_len - 1) - (end_bit - 1);
self.masks[start_mask_index] &= ~(mask1 & mask2);
mask1 = std.math.boolMask(MaskInt, value) << start_bit;
mask2 = std.math.boolMask(MaskInt, value) >> (mask_len - 1) - (end_bit - 1);
self.masks[start_mask_index] |= mask1 & mask2;
} else {
var bulk_mask_index: usize = undefined;
if (start_bit > 0) {
self.masks[start_mask_index] =
(self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
(std.math.boolMask(MaskInt, value) << start_bit);
bulk_mask_index = start_mask_index + 1;
} else {
bulk_mask_index = start_mask_index;
}
while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
}
if (end_bit > 0) {
self.masks[end_mask_index] =
(self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
(std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
}
}
}
/// Removes a specific bit from the bit set
pub fn unset(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] &= ~maskBit(index);
}
/// Flips a specific bit in the bit set
pub fn toggle(self: *Self, index: usize) void {
assert(index < bit_length);
if (num_masks == 0) return; // doesn't compile in this case
self.masks[maskIndex(index)] ^= maskBit(index);
}
/// Flips all bits in this bit set which are present
/// in the toggles bit set.
pub fn toggleSet(self: *Self, toggles: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* ^= toggles.masks[i];
}
}
/// Flips every bit in the bit set.
pub fn toggleAll(self: *Self) void {
for (&self.masks) |*mask| {
mask.* = ~mask.*;
}
// Zero the padding bits
if (num_masks > 0) {
self.masks[num_masks - 1] &= last_item_mask;
}
}
/// Performs a union of two bit sets, and stores the
/// result in the first one. Bits in the result are
/// set if the corresponding bits were set in either input.
pub fn setUnion(self: *Self, other: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* |= other.masks[i];
}
}
/// Performs an intersection of two bit sets, and stores
/// the result in the first one. Bits in the result are
/// set if the corresponding bits were set in both inputs.
pub fn setIntersection(self: *Self, other: Self) void {
for (&self.masks, 0..) |*mask, i| {
mask.* &= other.masks[i];
}
}
/// Finds the index of the first set bit.
/// If no bits are set, returns null.
pub fn findFirstSet(self: Self) ?usize {
var offset: usize = 0;
const mask = for (self.masks) |mask| {
if (mask != 0) break mask;
offset += @bitSizeOf(MaskInt);
} else return null;
return offset + @ctz(mask);
}
/// Finds the index of the last set bit.
/// If no bits are set, returns null.
pub fn findLastSet(self: Self) ?usize {
if (bit_length == 0) return null;
const bs = @bitSizeOf(MaskInt);
var len = bit_length / bs;
if (bit_length % bs != 0) len += 1;
var offset: usize = len * bs;
var idx: usize = len - 1;
while (self.masks[idx] == 0) : (idx -= 1) {
offset -= bs;
if (idx == 0) return null;
}
offset -= @clz(self.masks[idx]);
offset -= 1;
return offset;
}
/// Finds the index of the first set bit, and unsets it.
/// If no bits are set, returns null.
pub fn toggleFirstSet(self: *Self) ?usize {
var offset: usize = 0;
const mask = for (&self.masks) |*mask| {
if (mask.* != 0) break mask;
offset += @bitSizeOf(MaskInt);
} else return null;
const index = @ctz(mask.*);
mask.* &= (mask.* - 1);
return offset + index;
}
/// Returns true iff every corresponding bit in both
/// bit sets are the same.
pub fn eql(self: Self, other: Self) bool {
var i: usize = 0;
return while (i < num_masks) : (i += 1) {
if (self.masks[i] != other.masks[i]) {
break false;
}
} else true;
}
/// Returns true iff the first bit set is the subset
/// of the second one.
pub fn subsetOf(self: Self, other: Self) bool {
return self.intersectWith(other).eql(self);
}
/// Returns true iff the first bit set is the superset
/// of the second one.
pub fn supersetOf(self: Self, other: Self) bool {
return other.subsetOf(self);
}
/// Returns the complement bit sets. Bits in the result
/// are set if the corresponding bits were not set.
pub fn complement(self: Self) Self {
var result = self;
result.toggleAll();
return result;
}
/// Returns the union of two bit sets. Bits in the
/// result are set if the corresponding bits were set
/// in either input.
pub fn unionWith(self: Self, other: Self) Self {
var result = self;
result.setUnion(other);
return result;
}
/// Returns the intersection of two bit sets. Bits in
/// the result are set if the corresponding bits were
/// set in both inputs.
pub fn intersectWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other);
return result;
}
/// Returns the xor of two bit sets. Bits in the
/// result are set if the corresponding bits were
/// not the same in both inputs.
pub fn xorWith(self: Self, other: Self) Self {
var result = self;
result.toggleSet(other);
return result;
}
/// Returns the difference of two bit sets. Bits in
/// the result are set if set in the first but not
/// set in the second set.
pub fn differenceWith(self: Self, other: Self) Self {
var result = self;
result.setIntersection(other.complement());
return result;
}
/// Iterates through the items in the set, according to the options.
/// The default options (.{}) will iterate indices of set bits in
/// ascending order. Modifications to the underlying bit set may
/// or may not be observed by the iterator.
pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
return Iterator(options).init(&self.masks, last_item_mask);
}
pub fn Iterator(comptime options: IteratorOptions) type {
return GenericIterator(MaskInt, options);
}
fn maskBit(index: usize) MaskInt {
return @as(MaskInt, 1) << @as(ShiftInt, @truncate(index));
}
fn maskIndex(index: usize) usize {
return index >> @bitSizeOf(ShiftInt);
}
fn boolMaskBit(index: usize, value: bool) MaskInt {
return @as(MaskInt, @intFromBool(value)) << @as(ShiftInt, @intCast(index));
}
};
}