While doing Advent of Code, when I tried to use
StaticBitSet, I was surprised it was missing a function to determine if one
StaticBitSet is the subset of another.
My solution required to check if a pair of sets were either a subset of one or the other. I.E. given sets
a ⊂ b or b ⊂ a.
StaticBitSet functionality, I implemented this as:
const a: std.StaticBitSet... const b: std.StaticBitSet... var ab_intersection = a; ab_intersection.setIntersection(b); const either_subset_of = ab_intersection.mask == a.mask or ab_intersection.mask == b.mask;
The next day I set out to see how difficult it would be to make a contribution to
std.StaticBitSet to add
subsetOf. It turns out the process is pretty simple and the actual experience was amazing.
std is well organized and
zig test lib/std/bit_set.zig just works.
I was able hammer out a complete pull request with full documentation and tests.
I decided to add a series of pure functions:
fn eql(self: Self, other: Self) bool fn subsetOf(self: Self, other: Self) bool fn supersetOf(self: Self, other: Self) bool fn complement(self: Self) Self fn unionWith(self: Self, other: Self) Self fn intersectWith(self: Self, other: Self) Self fn xorWith(self: Self, other: Self) Self fn differenceWith(self: Self, other: Self) Self
Aside: I couldn't use the fn name
unionas that is a keyword. For consistency I decided to append
Withfor all the set operators.
comptime, there are far fewer edge cases to handle. In other languages to implement
eql one would need to ensure the
bit_length of the two sets are the same, but since
comptime if one tried to write
std.StaticBitSet(1).initFull().eql(std.StaticBitSet(2).initFull()), one would get a compiler error instead of a run-time error!
With these new functions, my original subset problem is simplified down to:
const a: std.StaticBitSet... const b: std.StaticBitSet... const either_subset_of = a.subsetOf(b) or b.subsetOf(a);
Nice post, and glad to know that contributing to std is such a smooth experience.
Just a small nitpick: do you really need to compute the set intersection twice to perform the required test? It seems to me that computing it once and than comparing with both a and b could be enough.
Good point. I blindly inlined the implementation of
subsetOf, but you are right. I'll fix it.