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
: a ⊂ b or b ⊂ a
.
Using existing 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.
The 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
union
as that is a keyword. For consistency I decided to appendWith
for all the set operators.
Since std.StaticBitSet
is 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 bit_length
is 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);
Top comments (2)
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.